Eulerian polynomials

The Eulerian polynomials were introduced by Leonhard Euler in his Remarques sur un beau rapport entre les séries des puissances tant directes que réciproques in 1749 (first printed in 1765) where he describes a method of computing values of the zeta function at negative integers by a precursor of Abel's theorem applied to a divergent series.

Definition

The Eulerian polynomials are defined by the exponential generating function

$\sum _{n=0}^{\infty }A_{n}(t)\,{\frac {x^{n}}{n!}}={\frac {t-1}{t-\exp((t-1)\,x)}}.$

The Eulerian polynomials can be computed by the recurrence

$A_{0}(t)=1,\,$

$A_{n}(t)=t\,(1-t)\,A_{n-1}^{'}(t)+A_{n-1}(t)\,(1+(n-1)\,t),\quad n\geq 1.$

An equivalent way to write this definition is to set the Eulerian polynomials inductively by

$A_{0}(t)=1,\,$

$A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}\,A_{k}(t)\,(t-1)^{n-1-k},\quad n\geq 1.$

The definition given is used by major authors like D. E. Knuth, D. Foata and F. Hirzebruch. In the older literature (for example in L. Comtet, Advanced Combinatorics) a slightly different definition is used, namely

$C_{0}(t)=1,\,$

$C_{n}(t)=t\,(1-t)\,C_{n-1}^{'}(t)+C_{n-1}(t)\,(nt),\quad n\geq 1.$

The sequence of Eulerian polynomials $\scriptstyle A_{n}(x)$ has ordinary generating function given by the continued fraction

${\cfrac {1}{1-t-{\cfrac {x\,t^{2}}{1-(2+x)\,t-{\cfrac {4x\,t^{2}}{1-(3+2x)\,t-{\cfrac {9x\,t^{2}}{1-(4+3x)\,t-{\cfrac {16x\,t^{2}}{\ddots }}}}}}}}}}$

Three identities

An identity due to Euler is

$\sum _{j\geq 0}x^{j}(j+1)^{n}={\frac {A_{n}(x)}{(1-x)^{n+1}}}.$

For instance we get for $\scriptstyle n\,=\,0,1,2:$

$1+x+x^{2}+x^{3}+...={\frac {1}{1-x}},$

$1+2x+3x^{2}+4x^{3}+...={\frac {1}{(1-x)^{2}}},$

$1+2^{2}x+3^{2}x^{2}+4^{2}x^{3}+...={\frac {1+x}{(1-x)^{3}}}.$

Let $\scriptstyle \operatorname {S} (n,k)$ denote the Stirling numbers of the second kind. Frobenius proved that the Eulerian polynomials are equal to:

$A_{n}(x)=\sum _{k=1}^{n}k!\,\operatorname {S} (n,k)(x-1)^{n-k}\quad (n\geq 1).$

The third identity is called Worpitzky's identity

$x^{n}=\sum _{0\leq k<n}{\binom {x+k}{n}}[x^{k}]A_{n}(x).$

Here $\scriptstyle [x^{k}]A_{n}(x)$ denotes the coefficient of $\scriptstyle x^{k}$ in $\scriptstyle A_{n}(x)$.

Eulerian numbers

Main article page: Eulerian numbers

The coefficients of the Eulerian polynomials are the Eulerian numbers $\scriptstyle A_{n,k}\$,

$A_{n}(t)=\sum _{k=0}^{n-1}A_{n,k}\ t^{k}.$

This definition of the Eulerian numbers agrees with the combinatorial definition in the DLMF. The triangle of Eulerian numbers is also called Euler's triangle.

A173018 A(n,k) 0 1 2 3 4 0 1 0 0 0 0 1 1 0 0 0 0 2 1 1 0 0 0 3 1 4 1 0 0 4 1 11 11 1 0

A123125 C(n,k) 0 1 2 3 4 0 1 0 0 0 0 1 0 1 0 0 0 2 0 1 1 0 0 3 0 1 4 1 0 4 0 1 11 11 1

A008292 B(n,k)   1 2 3 4             1   1 0 0 0 2   1 1 0 0 3   1 4 1 0 4   1 11 11 1

Euler's definition A(n, k) is A173018. The main entry for the Eulerian numbers in the OEIS database is A008292. It enumerates like C(n, k) albeit restricted to n ≥ 1 and k ≥ 1.

A combinatorial interpretation

Let S_n denote the set of all bijections (one-to-one and onto functions) from {1, 2, …, n} to itself, call an element of S_n a permutation p and identify it with the ordered list p₁ p₂ … p_n.

Using the Iverson bracket notation [.] the number of ascents of p is defined as

$\operatorname {asc} (p)=\sum _{i=1}^{n}\left[\,p_{i}<p_{i+1}\,\right],$

where p_n+1 ← 0. The combinatorial interpretation of the Eulerian polynomials is then given by

$A_{n}(x)=\sum _{p\in S_{n}}x^{\operatorname {asc} (p)}.$

The table below illustrates this representation for the case n = 4.

p	asc	p	asc	p	asc	p	asc
4321	0	4231	1	2413	2	1423	2
3214	1	2431	1	2134	2	1342	2
3241	1	4312	1	2314	2	4123	2
3421	1	3142	1	2341	2	1324	2
4213	1	4132	1	3124	2	1243	2
2143	1	1432	1	3412	2	1234	3

The number of permutations of {1, 2, …, 2n} with n ascents (the central Eulerian numbers) are listed in A180056.

History

Eulerian polynomials in Institutiones calculi differentialis, 1755

Leonhard Euler introduced the polynomials in 1749 in the form

$\sum _{k=0}^{\infty }(k+1)^{n}\,t^{k}={\frac {A_{n}(t)}{(1-t)^{n+1}}}.$

Euler introduced the Eulerian polynomials in an attempt to evaluate the Dirichlet eta function

$\eta (s)=\sum _{n=1}^{\infty }{\frac {(-1)^{n-1}}{n^{s}}}$

at s = -1, -2, -3,... . This led him to conjecture the functional equation of the eta function (which immediately implies the functional equation of the zeta function). Most simply put, the relation Euler was after was

$A_{n}(-1)=(2^{n+1}-4^{n+1})\,\zeta (-n),\quad n\geq 0.$

Though Euler's reasoning was not rigorous by modern standards it was a milestone on the way to Riemann's proof of the functional equation of the zeta function. A short exposition of what Euler did was given by Keith Conrad on MathOverflow.

The facsimile shows Eulerian polynomials as given by Euler in his work Institutiones calculi differentialis, 1755. It is interesting to note that the original definition of Euler coincides with the definition in the DLMF.

Eulerian generating functions

We call a generating function an Eulerian generating function iff it has the form

$G_{n}(t)={\frac {g(t)A_{n}(t)}{(1-t)^{n+1}}},\quad n\geq 0,$

for some polynomial g(t). Many elementary classes of sequences have an Eulerian generating function. A few examples are collocated in the table below.

Generating function g(t)An(t) / (1- t)n+1	n = 0	n = 1	n = 2	n = 3	n = 4	n = 5
g(t) = 1 − t2	A019590	A040000	A008574	A005897	A008511	A008512
g(t) = 1 − t	A000007	A000012	A005408	A003215	A005917	A022521
g(t) = t	A057427	A001477	A000290	A000578	A000583	A000584
g(t) = 1 + t	A040000	A005408	A001844	A005898	A008514	A008515
g(t) = 1 + t + t2	A158799	A008486	A005918	A027602	A160827	A179995

For instance the case

• g(t) = t gives the generating function of the regular orthotopic numbers, and the case
• g(t) = 1 + t gives the generating function of the centered orthotopic numbers.

The roots of the polynomials

A1(x),  A2(x),  A3(x),  A4(x),  A5(x),  A6(x)

$\scriptstyle A_{n}(x)$ has only (negative and simple) real roots, a result due to Frobenius. In fact the Eulerian polynomials form a Sturm sequence, that is, $\scriptstyle A_{n+1}(x)$ has n real roots separated by the roots of $\scriptstyle A_{n}(x)$.

Special values of the Eulerian polynomials

x	−1/2	1/2	3/2
2nAn(x)	A179929	A000629	A004123
x	−2	−1	0
An(x)	A087674	A155585	A000012
x	1	2	3
An(x)	A000142	A000670	A122704

Assorted sequences and formulae

Let ∂r denote the denominator of a rational number r.

A122778	An(n)
A180085	An(−n)
A000111	An(I)(1+I)(1-n)
A006519	∂(An(−1) / 2n)
A001511	log2(∂(A2n+1(−1) / 22n+1))

Eulerian polynomials A_n(x) and Euler polynomials E_n(x) have a sequence of values in common (up to a binary shift). Let B_n(x) denote the Bernoulli polynomials and ζ(n) the Riemann Zeta function.  $\scriptstyle \left\{{n \atop k}\right\}\,$ denotes the Stirling numbers of the second kind. The formulas below show how rich in content the Eulerian polynomials are.

A155585 for all n ≥ 0
	$\quad A_{n}(-1)\quad$
	$=E_{n}(1)2^{n}\quad$
	$=\zeta (-n)(2^{n+1}-4^{n+1})\quad$
	$=B_{n+1}(1){\frac {(4^{n+1}-2^{n+1})}{(n+1)}}\quad$
	$=\sum _{k=0}^{n}\left\{{n \atop k}\right\}(-2)^{n-k}k!\quad$
	$=\sum _{k=0}^{n}\sum _{v=0}^{k}{\binom {k}{v}}(-1)^{v}2^{n-k}(v+1)^{n}\quad$

The connection with the polylogarithm

Eulerian polynomials are related to the polylogarithm

$\operatorname {Li} _{s}(z)=\sum _{k=1}^{\infty }{z^{k} \over k^{s}}.$

For nonpositive integer values of s, the polylogarithm is a rational function. The first few are

$\operatorname {Li} _{0}(z)\ \;={z \over 1-z};\ \quad \quad \operatorname {Li} _{-1}(z)={z \over (1-z)^{2}};$

$\operatorname {Li} _{-2}(z)={z(1+z) \over (1-z)^{3}};\quad \ \operatorname {Li} _{-3}(z)={z(1+4z+z^{2}) \over (1-z)^{4}}.$

A plot of these functions in the complex plane is given in the gallery below.

Different polylogarithm functions in the complex plane

$\operatorname {Li} _{0}(z)$	$\operatorname {Li} _{-1}(z)$	$\operatorname {Li} _{-2}(z)$	$\operatorname {Li} _{-3}(z)$

In general the explicit formula for nonpositive integer s is

$\operatorname {Li} _{-n}(z)={{zA_{n}(z)} \over (1-z)^{n+1}}\qquad (n\geq 0)~.$

See also DLMF and the section on series representations of the polylogarithm on Wikipedia. However, note that the conventions on Wikipedia do not conform to the DLMF definition of the Eulerian polynomials.

Program

(Maple)
a := proc(n,m) local k; 
     add((-1)^k*binomial(n+1,k)*(m+1-k)^n,k=0..m) 
     end:
A := proc(n,x) local k; 
     `if`(n=0,1,add(a(n,k)*x^k,k=0..n-1)) 
     end:

(Sage)
def a(n, m) :
    return sum((-1)^k*binomial(n+1,k)*(m+1-k)^n for k in (0..m))
def A(n, x) :
    if n == 0 : return 1
    return sum(a(n,k)*x^k for k in (0..n-1))

Notes

References

• P. Barry, Eulerian Polynomials as Moments, via Exponential Riordan Arrays, Journal of Integer Sequences, Vol. 14 (2011), Article 11.9.5.
• K. Conrad, Answer to: Historical question in analytic number theory, MathOverflow, Jan 29 2010.
• Leonhard Euler, E352 (Eneström Index), Remarques sur un beau rapport entre les séries des puissances tant directes que réciproques, 1768., The Euler Archive.
• Leonhard Euler, E212 (Eneström Index), Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum (Foundations of Differential Calculus, with Applications to Finite Analysis and Series), 1755., The Euler Archive.
• Dominique Foata and Marcel-Paul Schützenberger, Théorie Géométrique des Polynômes Eulériens, 1970, arXiv:math.CO/0508232.
• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 1989.
• Friedrich Hirzebruch, Eulerian polynomials, Münster J. of Math. 1 (2008), 9–14.
• Dominique Foata, Eulerian Polynomials: from Euler's Time to the Present. Invited address at the 10-th Annual Ulam Colloquium, University of Florida, February 18, 2008.

See also

• P. Luschny, Generalized Eulerian Polynomials.