Eulerian-type polynomials
Descent and peak polynomials of derangements, words and permutations are real-rooted, and consecutive members of most families interlace.
Results
Results 1 to 7 are the theorems of [Ale26], in the order of the paper. Result 8 concerns the zig-zag Eulerian polynomials.
- Derangements. For $n\ge2$, the polynomial $\sum_{\pi\in\mathfrak D_n}x^{\operatorname{des}\pi}$ over derangements is nonzero and real-rooted with all roots nonpositive.
- Balanced cyclic words. For $n\ge1$, let $w$ range over binary words of length $2n$ with exactly $n$ ones, and let $\operatorname{cdes}w$ count the cyclic positions $i$ with $w_i=1$ and $w_{i+1}=0$. Then $\sum_w x^{\operatorname{cdes}w}$ is real-rooted with simple roots: one root is $0$ and the other $n-1$ are negative. This polynomial is $$C_n(x)=\sum_{k=1}^n2\binom nk\binom{n-1}{k-1}x^k=\frac2n\,x\,B_n'(x),$$ where $B_n(x)=\sum_k\binom nk^2x^k$ is the type $B$ Narayana polynomial.
- Even-top descents. Let $\operatorname{edes}\pi$ count the descents $\pi_j>\pi_{j+1}$ with $\pi_j$ even. For $n\ge2$, the polynomial $\sum_{\pi\in\mathfrak S_n}x^{\operatorname{edes}\pi}$ is real-rooted with negative roots. It strictly alternates with the same polynomial for $n+1$: both have simple roots, no root is shared, and one interlaces the other.
- Super-Eulerian polynomials. Let $E^{(\ell)}_{1,0}=1$ and $E^{(\ell)}_{n,k}=(k+1)^\ell E^{(\ell)}_{n-1,k}+(n-k)^\ell E^{(\ell)}_{n-1,k-1}$, with entries outside $0\le k\le n-1$ equal to zero, and let $A^{(\ell)}_n=\sum_{k<n}E^{(\ell)}_{n,k}x^k$. For $\ell\ge1$ and $n\ge0$, the polynomial $A^{(\ell)}_{n+1}$ is real-rooted with nonpositive roots, and $A^{(\ell)}_{n+1}\ll A^{(\ell)}_{n+2}$ with no common root. Moreover $$A^{(\ell)}_{n+1}(x)=\sum_{0\le i\le n/2}\gamma_i\,x^i(1+x)^{n-2i},$$ where $\gamma$ is nonzero, real-rooted, with nonpositive roots and nonnegative coefficients.
- Ternary words. For $w\in\{0,1,2\}^n$, let $\operatorname{run}w$ be the number of maximal strictly increasing runs. Then $T_n(x)=\sum_w x^{\operatorname{run}w}$ is a Pólya frequency polynomial and $T_n\ll T_{n+1}$. These polynomials satisfy $T_0=1$ and $$(n+1)\,T_{n+1}=3x(1-x)\,T_n'+\bigl((4n+3)x-n\bigr)\,T_n.$$
- Peaks. For $n\ge1$, the polynomial $\sum_{\pi\in\mathfrak S_n}x^{\operatorname{pk}\pi}$, where $\operatorname{pk}$ counts interior peaks, is real-rooted. For $n\ge3$ it has degree $\lfloor(n-1)/2\rfloor$ and negative roots, and it strictly alternates with the same polynomial for $n+1$.
- Peak values. Let $K_n(z_1,\dots,z_n)=\sum_{\pi\in\mathfrak S_n}\prod z_v$, with $v$ ranging over the values of the interior peaks of $\pi$. Then $K_n$ is real stable for every $n$. For $n\ge1$ and positive weights $w_1,\dots,w_{n+1}$, the polynomial $K_n(w_1x,\dots,w_nx)$ interlaces $K_{n+1}(w_1x,\dots,w_{n+1}x)$.
- Zig-zag swaps. Call $i$ a swap of a permutation $\pi$ of $[n]$ if $\pi^{-1}(i)+1<\pi^{-1}(i+1)$, and let $\operatorname{swap}\pi$ be the number of swaps. For $n\ge1$, the polynomial $\sum x^{\operatorname{swap}\pi}$ over up-down permutations $\pi_1<\pi_2>\pi_3<\dotsb$ is nonzero with simple negative roots, and has degree $n-2$ for $n\ge2$.
Euler insertion operators. Let $$ E_{c,d}\,p=\bigl(c+(d+1)x\bigr)\,p+(x-x^2)\,p' . $$
Theorem (mixed compatibility). Let $f,g$ have nonnegative coefficients and positive leading coefficients, with $g\ll f$, $\deg f=\deg g+1$ and $\deg f\le n+1$. Then $E_{1,n}\,g$ and $E_{0,n+1}\,f$ are compatible: every nonnegative combination of them is zero or real-rooted. In particular $E_{0,n+1}f+\lambda\,E_{1,n}g$ is real-rooted for every $\lambda>0$.
Theorem (oriented completion). Let $L_Mp=Mp+(1-x)p'$. If $p\ll q$ are Pólya frequency polynomials of the same degree $D\ge1$ and $M\ge D+1$, then $L_Mp\ll L_Mq$. Moreover, if $p$ and $p+1$ are Pólya frequency polynomials of degree $D\ge2$ and $M\ge D+2$, the four polynomials $$ E_{1,M-2}\,p,\quad E_{1,M-2}(p+1),\quad E_{0,M-1}\,p,\quad E_{0,M-1}(p+1) $$ have a common left interleaver.
Proof
The two operator theorems give the proof for derangement descents.
References
- [Ale26]
- [Sha26, Theorem C], for the absence of common roots in result 4.
- [Ale26] Real-rooted Eulerian polynomials from permutations, words, and paths. arXiv e-prints, 2026.
BibTeX
@article{Alexandersson2026Eulerian, author = {Per Alexandersson}, title = {Real-rooted {E}ulerian polynomials from permutations, words, and paths}, year = {2026}, eprint = {2609.07325v2}, url = {https://arxiv.org/abs/2609.07325v2}, journal = {arXiv e-prints} } - [Sha26, Theorem C] Multivariate stability of powered triangular recurrences and parametrised Eulerian polynomials. arXiv e-prints, 2026.
BibTeX
@article{Shankar2026x, author = {Umesh Shankar}, title = {Multivariate stability of powered triangular recurrences and parametrised {E}ulerian polynomials}, year = {2026}, eprint = {2609.15651v1}, url = {https://arxiv.org/abs/2609.15651v1}, journal = {arXiv e-prints} }