Descent polynomials of separable permutations
For $n\ge2$ the descent polynomials of the separable permutations of $[n]$ and $[n+1]$ interlace and have no common root; the same holds for their gamma-polynomials. The proof transfers interlacing through factorial compression, which maps polynomials with negative roots to strictly interlacing pairs.
Results
A permutation is separable if it avoids $2413$ and $3142$. Let $S_n(t)=\sum_\pi t^{\operatorname{des}\pi}$ over the separable permutations $\pi$ of $[n]$. Fu, Lin and Zeng [FLZ18] give the gamma-polynomials $\Gamma_n$ of $S_n$: $$ S_n(t)=(1+t)^{n-1}\,\Gamma_n\bigl(t/(1+t)^2\bigr). $$ For integers $N\ge1$ and $0\le\ell\le N$, the level-$\ell$ factorial compression of $p=\sum_kp_kx^k$ is $$ C_{N,\ell}\,p=\sum_{k\le N,\ 2k\le N+\ell}\frac{(N-k)!}{(N+\ell-2k)!}\,p_k\,x^k , $$ and for $a\in\mathbb R$ we put $E_ap=(x+a)p+xp'$. Zhang [Zha26] represents $\Gamma_{N+2}$ as the level-one factorial compression of $B_N$, where $B_0=1$ and $B_{N+1}=E_{(N+2)/2}B_N$; here $\Gamma_0=0$, $\Gamma_1=1$, $\Gamma_2=1$ and $\Gamma_3=1+2x$.
Theorem (Zhang). For $n\ge2$:
- $S_n\ll S_{n+1}$ without a common root;
- $\Gamma_n\ll\Gamma_{n+1}$ without a common root;
- $S_n$ has only simple negative roots, and $\deg S_n=n-1$.
Also $B_N\ll B_{N+1}$ without a common root, for $N\ge0$.
Theorem (identification). The descent enumerator of the separable permutations of $[n+1]$ equals $S_{n+1}$ as defined through $\Gamma_{n+1}$, for $n\ge0$. Hence $S_n\ll S_{n+1}$ for the permutation statistic. The gamma-polynomials satisfy, for $n\ge2$ and $\Gamma_0=0$, $$ \Gamma_n=\Gamma_{n-1}+x\sum_{i+j=n-1}\Gamma_i\Gamma_j+x\sum_{i+j+l=n}\Gamma_i\Gamma_j\Gamma_l , $$ that is, $G=\sum_n\Gamma_nw^n$ satisfies $G=w+wG+xwG^2+xG^3$ [FLZ18].
Theorem (factorial compression). [Zha26] Let $N\ge1$, $0\le\ell\le N$ and $a>0$, and let $p$ be a real-rooted polynomial of degree $N$ with positive leading coefficient and only negative roots, which may be repeated. Then $C_{N,\ell}\,p$ and $C_{N+1,\ell}\,E_ap$ have degrees $\lfloor(N+\ell)/2\rfloor$ and $\lfloor(N+\ell+1)/2\rfloor$ and simple negative roots, and $C_{N,\ell}\,p\ll C_{N+1,\ell}\,E_ap$ with no common root.
The compression is a Schur–Szegő composition with an explicit kernel, $C_{N,\ell}\,p=\frac{N!}{(N+\ell)!}\,h_{N+\ell}*_Np$ with $h_r=\sum_{j\le r/2}\frac{r!}{j!\,(r-2j)!}x^j$, and Schur–Szegő composition with a polynomial with only negative roots preserves interlacing without common roots.
Proof
The enumerators $S_n$ satisfy the cubic recurrence $S_n=(1+t)S_{n-1}+t\sum_{i+j=n-1}S_iS_j+t\sum_{i+j+l=n}S_iS_jS_l$, from the decomposition of a separable permutation into direct and skew sums, and the gamma substitution carries the cubic for $\Gamma_n$, proved by Lagrange inversion, to this one. Interlacing holds for $B_N$ by the derivative-lag recurrence, and the factorial compression theorem with $\ell=1$ and $a=(N+2)/2$ transfers it to $\Gamma_{N+2}$ and $\Gamma_{N+3}$. The gamma substitution then transfers it to $S_n$ and $S_{n+1}$: the two branches of $\rho\mapsto\rho/(1+\rho)^2$ carry a common root of the descent polynomials to a common root of the gamma-polynomials, and the root $-1$ is excluded by evaluating the gamma transform there.
References
- [Zha26] Strict Interlacing of the Descent Polynomials of Separable Permutations. 2026.
BibTeX
@unpublished{Zhang2026SeparableInterlacing, author = {Zhang, Zhanhe}, title = {Strict Interlacing of the Descent Polynomials of Separable Permutations}, date = {2026-09-10}, year = {2026}, note = {SSRN preprint 7510941, posted September 25, 2026}, doi = {10.2139/ssrn.7510941}, url = {https://ssrn.com/abstract=7510941} } - [FLZ18] On two unimodal descent polynomials. Discrete Mathematics, 341(9), 2616-2626, 2018.
BibTeX
@article{FuLinZeng2018, author = {Fu, Shishuo and Lin, Zhicong and Zeng, Jiang}, title = {On two unimodal descent polynomials}, year = {2018}, journal = {Discrete Mathematics}, volume = {341}, number = {9}, pages = {2616--2626}, publisher = {Elsevier BV}, doi = {10.1016/j.disc.2018.06.010}, url = {https://doi.org/10.1016/j.disc.2018.06.010}, issn = {0012-365X} }