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

See also Eulerian polynomials on symmetricfunctions.com.

  1. [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}
    }
  2. [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}

    RealRooted.eulerianTildesource
    def eulerianTilde : Nat → ℝ[X]
      | 0 => X
      | n + 1 =>
          X * (C (n + 2 : ℝ) * eulerianTilde n +
            (1 - X) * (eulerianTilde n).derivative)
  • Type B Eulerian polynomials

    RealRooted.typeBEuleriansource
    def typeBEulerian : Nat → ℝ[X]
      | 0 => 1
      | n + 1 =>
          typeBEulerianCoeffA n * typeBEulerian n +
            typeBEulerianCoeffB * (typeBEulerian n).derivative
  • Generalized Eulerian polynomials

    RealRooted.generalizedEuleriansource
    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

    RealRooted.isRealRooted_eulerianTildesource
    theorem isRealRooted_eulerianTilde : ∀ n : Nat,
        ((eulerianTilde n) ≠ 0 ∧ (eulerianTilde n).Splits)
  • Consecutive Eulerian polynomials interlace

    RealRooted.interlaces_eulerianTilde_succsource
    theorem interlaces_eulerianTilde_succ (n : Nat) :
        Interlaces (eulerianTilde n) (eulerianTilde (n + 1))
  • Type B Eulerian polynomials are real-rooted

    RealRooted.isRealRooted_typeBEuleriansource
    theorem isRealRooted_typeBEulerian :
        ∀ n : Nat, ((typeBEulerian n) ≠ 0 ∧ (typeBEulerian n).Splits)
  • Consecutive type B Eulerian polynomials interlace

    RealRooted.interlaces_typeBEulerian_succsource
    theorem interlaces_typeBEulerian_succ (n : Nat) :
        Interlaces (typeBEulerian n) (typeBEulerian (n + 1))
  • For c > 0, E_n^{(c)} is real-rooted

    RealRooted.generalizedEulerian_splitssource
    theorem generalizedEulerian_splits (hc : 0 < c) (n : ℕ) :
        (generalizedEulerian c n).Splits
  • For c > 0, E_n^{(c)} interlaces E_{n+1}^{(c)}Main result

    RealRooted.interlaces_generalizedEulerian_succsource
    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)}

    RealRooted.eulerianTilde_eq_X_mul_generalizedEulerian_onesource
    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)}

    RealRooted.typeBEulerian_eq_generalizedEulerian_twosource
    theorem typeBEulerian_eq_generalizedEulerian_two (n : ℕ) :
        typeBEulerian n = generalizedEulerian 2 n
  • Alternating-sum formula for the coefficients of E_n^{(1)}

    RealRooted.GeneralizedEulerian.coeff_generalizedEulerian_one_eq_sumsource
    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)}

    RealRooted.genPoly_univ_descentCountsource
    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

    RealRooted.isRealRooted_genPoly_univ_descentCountsource
    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

    RealRooted.eval_neg_generalizedEulerian_one_possource
    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.