Eulerian polynomials
The Eulerian polynomials, the type $B$ Eulerian polynomials and a one-parameter family containing both are real-rooted, and consecutive members interlace.
Results
For real $c$, the generalized Eulerian polynomials are $E^{(c)}_0=1$ and $$ E^{(c)}_{n+1}=\bigl(1+(cn+1)t\bigr)E^{(c)}_n+c\,t(1-t)\bigl(E^{(c)}_n\bigr)'. $$
Theorem (generalized Eulerian polynomials). For $c>0$ and $n\ge0$, $E^{(c)}_n$ is nonzero and real-rooted, and $E^{(c)}_n\ll E^{(c)}_{n+1}$.
Eulerian polynomials ($c=1$). Let $A_n(t)=\sum_{\sigma\in\mathfrak S_n}t^{\operatorname{des}\sigma}$. Then $E^{(1)}_n=A_{n+1}$. Hence $A_{n+1}$ is real-rooted and $A_{n+1}\ll A_{n+2}$. The shifted polynomials $P_n=tE^{(1)}_n$ satisfy $P_0=t$ and $P_{n+1}=t\bigl((n+2)P_n+(1-t)P_n'\bigr)$, and are real-rooted with $P_n\ll P_{n+1}$. For $j\ge0$, $$ [t^j]\,E^{(1)}_n=\sum_{i=0}^{j+1}(-1)^{j+1-i}\binom{n+2}{j+1-i}\,i^{\,n+1}. $$
Type $B$ Eulerian polynomials ($c=2$). The polynomials $B_n=E^{(2)}_n$ are given by $B_0=1$ and $B_{n+1}=\bigl(1+(2n+1)t\bigr)B_n+2t(1-t)B_n'$. They are real-rooted, and $B_n\ll B_{n+1}$.
Since $E^{(1)}_n$ is a Pólya frequency polynomial with constant coefficient $1$ and linear coefficient $2^{n+1}-n-2$, we have $E^{(1)}_n(-q)>0$ for $q>0$ with $q\,2^{n+1}\le1$.
References
- [Fro10], for the Eulerian recurrence and its real-rootedness.
- [Bre94], for type $B$.
See also Eulerian polynomials on symmetricfunctions.com.
- [Bre94] Francesco Brenti. q-Eulerian Polynomials Arising from Coxeter Groups. European Journal of Combinatorics, 15(5), 417-441, 1994.
BibTeX
@article{Brenti1994,
author = {Brenti, Francesco},
title = {q-{E}ulerian {P}olynomials {A}rising from {C}oxeter {G}roups},
year = {1994},
journal = {European Journal of Combinatorics},
volume = {15},
number = {5},
pages = {417--441},
doi = {10.1006/eujc.1994.1046},
url = {https://doi.org/10.1006/eujc.1994.1046}
}
- [Fro10] G Frobenius. Über die Bernoullischen und die Eulerschen Polynome. Sitzungsberichte der Preussische Akademie der Wissenschaften, 809-847, 1910.
BibTeX
@article{Frobenius1910,
title={{\"{U}}ber die {B}ernoullischen und die {E}ulerschen {P}olynome},
author={Frobenius, G},
journal={Sitzungsberichte der Preussische Akademie der Wissenschaften},
pages={809--847},
year={1910}
}
≔ Definitions
Shifted Eulerian polynomials P_n = t A_{n+1}
def eulerianTilde : Nat → ℝ[X]
| 0 => X
| n + 1 =>
X * (C (n + 2 : ℝ) * eulerianTilde n +
(1 - X) * (eulerianTilde n).derivative)
Type B Eulerian polynomials
def typeBEulerian : Nat → ℝ[X]
| 0 => 1
| n + 1 =>
typeBEulerianCoeffA n * typeBEulerian n +
typeBEulerianCoeffB * (typeBEulerian n).derivative
Generalized Eulerian polynomials
def generalizedEulerian (c : ℝ) : ℕ → ℝ[X]
| 0 => 1
| n + 1 =>
(1 + C (c * (n : ℝ) + 1) * X) * generalizedEulerian c n
+ C c * X * (1 - X) * (generalizedEulerian c n).derivative
⊢ Theorems
Eulerian polynomials are real-rooted
theorem isRealRooted_eulerianTilde : ∀ n : Nat,
((eulerianTilde n) ≠ 0 ∧ (eulerianTilde n).Splits)
Consecutive Eulerian polynomials interlace
theorem interlaces_eulerianTilde_succ (n : Nat) :
Interlaces (eulerianTilde n) (eulerianTilde (n + 1))
Type B Eulerian polynomials are real-rooted
theorem isRealRooted_typeBEulerian :
∀ n : Nat, ((typeBEulerian n) ≠ 0 ∧ (typeBEulerian n).Splits)
Consecutive type B Eulerian polynomials interlace
theorem interlaces_typeBEulerian_succ (n : Nat) :
Interlaces (typeBEulerian n) (typeBEulerian (n + 1))
For c > 0, E_n^{(c)} is real-rooted
theorem generalizedEulerian_splits (hc : 0 < c) (n : ℕ) :
(generalizedEulerian c n).Splits
For c > 0, E_n^{(c)} interlaces E_{n+1}^{(c)}Main result
theorem interlaces_generalizedEulerian_succ {c : ℝ} (hc : 0 < c) (n : ℕ) :
Interlaces (generalizedEulerian c n) (generalizedEulerian c (n + 1))
The shifted Eulerian polynomial P_n equals t E_n^{(1)}
theorem eulerianTilde_eq_X_mul_generalizedEulerian_one (n : ℕ) :
eulerianTilde n = X * generalizedEulerian 1 n
The type B Eulerian polynomial B_n equals E_n^{(2)}
theorem typeBEulerian_eq_generalizedEulerian_two (n : ℕ) :
typeBEulerian n = generalizedEulerian 2 n
Alternating-sum formula for the coefficients of E_n^{(1)}
theorem coeff_generalizedEulerian_one_eq_sum (k j : ℕ) :
(generalizedEulerian 1 k).coeff j =
∑ i ∈ Finset.range (j + 2),
(i : ℝ) ^ (k + 1) *
((-1 : ℝ) ^ (j + 1 - i) * (((k + 2).choose (j + 1 - i) : ℝ)))
The descent polynomial of permutations of n+1 letters is E_n^{(1)}
theorem genPoly_univ_descentCount (n : ℕ) :
(Finset.genPoly (Finset.univ : Finset (Equiv.Perm (Fin (n + 1))))
Equiv.Perm.descentCount : ℝ[X]) = generalizedEulerian 1 n
The descent polynomial of permutations of n+1 letters is real-rooted
theorem isRealRooted_genPoly_univ_descentCount (n : ℕ) :
(Finset.genPoly (Finset.univ : Finset (Equiv.Perm (Fin (n + 1))))
Equiv.Perm.descentCount : ℝ[X]) ≠ 0 ∧
Polynomial.Splits
(Finset.genPoly (Finset.univ : Finset (Equiv.Perm (Fin (n + 1))))
Equiv.Perm.descentCount : ℝ[X])
E_n^{(1)}(-q) > 0 whenever q > 0 and q 2^(n+1) ≤ 1
theorem eval_neg_generalizedEulerian_one_pos {n : ℕ} {q : ℝ} (hq : 0 < q)
(h : q * 2 ^ (n + 1) ≤ 1) : 0 < (generalizedEulerian 1 n).eval (-q)
Lean source RealRooted/Challenges/Combinatorial/Eulerian.lean at revision d6670742. Formalized 2026-07-10.