#Eulerian polynomials
For a permutation \(\sigma=\sigma_1\sigma_2\dotsb\sigma_n\in\symS_n,\) a descent is an index \(i\in[n-1]\) such that \(\sigma_i\gt{}\sigma_{i+1}.\) Write \(\des(\sigma)\) for the number of descents.
Definition (Eulerian polynomials and numbers).
For \(n\geq1,\) the Eulerian polynomial is \[A_n(t)\coloneqq\sum_{\sigma\in\symS_n}t^{\des(\sigma)} =\sum_{k=0}^{n-1}A(n,k)t^k,\] where the Eulerian number \(A(n,k)\) counts permutations in \(\symS_n\) with \(k\) descents. We set \(A_0(t)=1\) and take \(A(n,k)=0\) outside \(0\leq k\leq n-1.\)
The first polynomials are \[\begin{array}{c|l} n&A_n(t)\\ \hline 0&1\\ 1&1\\ 2&1+t\\ 3&1+4t+t^2\\ 4&1+11t+11t^2+t^3\\ 5&1+26t+66t^2+26t^3+t^4. \end{array}\] Their coefficients form the Eulerian triangle A008292; the version with a row for \(n=0\) and a terminal zero is A173018. The same numbers enumerate permutations by excedances. Inversion also shows that descents of \(\sigma^{-1}\) have the same distribution, although \(\des(\sigma)\) and \(\des(\sigma^{-1})\) need not agree for an individual permutation.
The classical monograph of Foata and Schützenberger [FS70] develops the combinatorial theory of Eulerian polynomials. Petersen’s modern account [Pet15] continues through gamma-positivity, polytopes, and Coxeter groups. See also [Sec. 1.4, Sta11].
#Recurrences
Inserting \(n\) into a permutation of \([n-1]\) gives \[A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1).\] Indeed, a permutation with \(k\) descents has \(k+1\) insertion slots that preserve this number. A permutation with \(k-1\) descents has \(n-k\) slots that create one new descent. Multiplying by \(t^k\) and summing gives the differential recurrence \[A_{n+1}(t)=(1+nt)A_n(t)+t(1-t)A'_n(t), \qquad A_0(t)=1.\] One also has the binomial recurrence \[A_n(t)=\sum_{j=0}^{n-1}\binom{n}{j}A_j(t)(t-1)^{n-1-j} \qquad(n\geq1).\]
#Generating functions and power sums
The exponential generating function is \[\sum_{n\geq0}A_n(t)\frac{x^n}{n!} =\frac{t-1}{t-\exp((t-1)x)}.\] As an identity of formal power series in \(t,\) \[\frac{A_n(t)}{(1-t)^{n+1}} =\sum_{j\geq0}(j+1)^n t^j.\] For \(|t|\lt{}1\) this is also an analytic identity. Thus, for \(n\geq1,\) \[\operatorname{Li}_{-n}(t) =\sum_{j\geq1}j^nt^j =\frac{tA_n(t)}{(1-t)^{n+1}}.\] This normalization explains why some references attach a factor \(t\) to the Eulerian polynomial: their numerator is \(tA_n(t)\) rather than \(A_n(t).\)
#Worpitzky’s identity and explicit formulas
The Eulerian numbers are the connection coefficients in Worpitzky’s identity \[x^n=\sum_{k=0}^{n-1}A(n,k)\binom{x+k}{n}.\] Equivalently, inclusion–exclusion gives \[A(n,k)=\sum_{j=0}^{k}(-1)^j\binom{n+1}{j}(k+1-j)^n.\] If \(S(n,k)\) denotes a Stirling number of the second kind, then \[A_n(t)=\sum_{k=1}^{n}k!S(n,k)t^{k-1}(1-t)^{n-k} \qquad(n\geq1).\] The exponent \(k-1\) in this formula is another place where the shifted and unshifted Eulerian conventions must not be mixed.
#Symmetry and special values
Complementing every value, or reversing the one-line notation, exchanges descents and ascents. Hence \[A(n,k)=A(n,n-1-k), \qquad t^{n-1}A_n(1/t)=A_n(t).\] In particular, \(A_n(t)\) is palindromic of degree \(n-1.\) Two useful evaluations are \[A_n(1)=n!, \qquad A_{2m}(-1)=0 \quad(m\geq1).\] For odd indices, \[A_{2m+1}(-1)=(-1)^m E_{2m+1},\] where \(E_n\) is the Euler zigzag number A000111. Thus the nonzero absolute values are the tangent numbers A000182; see [Ch. 5, FS70].
#Zeros, interlacing, and limit laws
Theorem (Frobenius, [Fro10]).
For \(n\geq2,\) the polynomial \(A_n(t)\) has \(n-1\) simple, strictly negative zeros. Moreover, the zeros of \(A_n(t)\) strictly interlace those of \(A_{n+1}(t).\)
The differential recurrence above gives a short inductive proof; see the Eulerian Sturm-sequence example for the root argument. Thus the Eulerian polynomials form a strict Sturm sequence of real-rooted polynomials. Real-rootedness implies log-concavity and unimodality of every Eulerian row. By the Aissen–Schoenberg–Whitney theorem, each row \((A(n,0),\dotsc,A(n,n-1)),\) extended by zeros, is also a Pólya frequency sequence. Consequently its Toeplitz matrix is totally non-negative; this is a TNN statement, not a strict total-positivity statement.
If \(D_n\) is the number of descents of a uniformly random permutation in \(\symS_n,\) then, for \(n\geq2,\) \[\operatorname{E}(D_n)=\frac{n-1}{2}, \qquad \operatorname{Var}(D_n)=\frac{n+1}{12}.\] Furthermore, \[\frac{D_n-(n-1)/2}{\sqrt{(n+1)/12}} \mathrel{\xrightarrow{\mathrm d}}\mathcal N(0,1).\] This is a classical instance of the central and local limit theory for real-rooted coefficient arrays; see [Ben73].
#Gamma-positivity
The palindromic symmetry above can be strengthened. For \(n\geq1\) there are non-negative integers \(\gamma_{n,k}\) such that \[A_n(t)=\sum_{k=0}^{\lfloor(n-1)/2\rfloor} \gamma_{n,k}t^k(1+t)^{n-1-2k}.\] Thus \(A_n(t)\) is gamma-positive; its gamma-vectors form A101280. The Foata–Strehl valley-hopping action gives a combinatorial proof and interpretation of the coefficients [FS70]. See [Ch. 4, Pet15] for a modern account.
#Polytope connections
Eulerian polynomials occur naturally as \(h\)- and \(h^*\)-polynomials.
The \(h\)-polynomial of the permutohedron \(\operatorname{Perm}_n\) is \(A_n(t).\) Equivalently, the Eulerian numbers form its \(h\)-vector.
The \(h^*\)-polynomial of the cube \([0,1]^n\) is \(A_n(t).\) Indeed, its Ehrhart series is \[\sum_{m\geq0}(m+1)^nt^m=\frac{A_n(t)}{(1-t)^{n+1}},\] which is the power-sum identity above.
The normalized volume of the hypersimplex \(\Delta_{k,n}\) is \(A(n-1,k-1).\) More refined descent–excedance formulas describe its \(h^*\)-polynomial; see [Li12].
#Generalizations
Several standard extensions retain part of this structure. Joint distributions such as \[\sum_{\sigma\in\symS_n}q^{\maj(\sigma)}t^{\des(\sigma)}\] give \(q\)-Eulerian, or Euler–Mahonian, polynomials and specialize to \(A_n(t)\) at \(q=1\); conventions vary, so the statistic and shift should always be stated. See [SW07] and the Eulerian quasisymmetric-function page. A multivariate stable refinement gives another route to the real-rootedness theorem.
For a finite Coxeter group \(W,\) one similarly considers \(\sum_{w\in W}t^{\des_W(w)}.\) The classical polynomials above are type \(A\); the type \(B\) and type \(D\) coefficient triangles are respectively A060187 and A066094. See the type \(B\) and \(D\) real-rootedness discussion and the Coxeter-groups page. Descent polynomials of linear extensions give the broader class of \(P\)-Eulerian polynomials.
Bibliography
- [Ben73]Edward A Bender. Central and local limit theorems applied to asymptotic enumeration. Journal of Combinatorial Theory, Series A, 15(1):91–111, July 1973.
.bib
@article{Bender1973, title = {Central and local limit theorems applied to asymptotic enumeration}, volume = {15}, ISSN = {0097-3165}, url = {http://dx.doi.org/10.1016/0097-3165(73)90038-1}, DOI = {10.1016/0097-3165(73)90038-1}, number = {1}, journal = {Journal of Combinatorial Theory, Series A}, publisher = {Elsevier BV}, author = {Bender, Edward A}, year = {1973}, month = jul, pages = {91–-111} } - [FS70]Dominique Foata and Marcel-Paul Schützenberger. Théorie géométrique des polynômes eulériens. arXiv:math/0508232, 138:1–94, 1970.
.bib
@book{FoataSchutzenberger1970, author = {Dominique Foata and Marcel-Paul Schützenberger}, title = {Th{\'e}orie g{\'e}om{\'e}trique des polyn{\^o}mes eul{\'e}riens}, series = {Lecture Notes in Mathematics}, volume = {138}, publisher = {Springer-Verlag}, address = {Berlin, Heidelberg, New York}, year = {1970}, pages = {1--94}, doi = {10.1007/BFb0060799}, eprint = {math/0508232} } - [Fro10]G Frobenius. Über die Bernoullischen und die Eulerschen Polynome. Sitzungsberichte der Preussische Akademie der Wissenschaften:809–847, 1910.
.bib
@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} } - [Li12]Nan Li. Ehrhart $h^*$-vectors of hypersimplices. Discrete & Computational Geometry, 48(4):847–878, 2012.
.bib
@article{Li2012, author = {Nan Li}, title = {Ehrhart {$h^*$}-vectors of hypersimplices}, year = {2012}, journal = {Discrete \& Computational Geometry}, volume = {48}, number = {4}, pages = {847--878}, doi = {10.1007/s00454-012-9452-2}, url = {https://doi.org/10.1007/s00454-012-9452-2} } - [Pet15]T. Kyle Petersen. Eulerian numbers. Birkhäuser advanced texts basler lehrbücher. Birkhäuser, 2015.
.bib
@book{Petersen2015EulerianNumbers, author = {T. Kyle Petersen}, title = {Eulerian Numbers}, series = {Birkhäuser Advanced Texts Basler Lehrbücher}, publisher = {Birkhäuser}, address = {New York}, year = {2015}, isbn = {978-1-4939-3091-3}, doi = {10.1007/978-1-4939-3091-3}, url = {https://doi.org/10.1007/978-1-4939-3091-3} } - [Sta11]Richard P. Stanley. Enumerative Combinatorics: Volume 1. Cambridge University Press, Second, 2011.
.bib
@book{StanleyEC1, author = {Richard P. Stanley}, title = {Enumerative {C}ombinatorics: {V}olume 1}, year = {2011}, isbn = {9781107602625}, edition = {Second}, doi = {10.1017/CBO9781139058520}, publisher = {Cambridge University Press} }