Eulerian number

In combinatorics, the Eulerian number A(n, m) is the number of permutations of the numbers 1 to n in which exactly m elements are greater than the previous element (permutations with m "ascents"). They are the coefficients of the Eulerian polynomials:

${\displaystyle A_{n}(t)=\sum _{m=0}^{n}A(n,m)\ t^{m}.}$

The Eulerian polynomials are defined by the exponential generating function

${\displaystyle \sum _{n=0}^{\infty }A_{n}(t)\cdot {\frac {x^{n}}{n!}}={\frac {t-1}{t-\mathrm {e} ^{(t-1)x}}}.}$

The Eulerian polynomials can be computed by the recurrence

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

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

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

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

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

Other notations for A(n, m) are E(n, m) and ${\displaystyle \scriptstyle \left\langle {n \atop m}\right\rangle }$.

History

Shows the polynomials presently known as Eulerian polynomials in Euler's work from 1755, Institutiones calculi differentialis, part 2, p. 485/6. The coefficients of these polynomials are known as Eulerian numbers.

In 1755 Leonhard Euler investigated in his book Institutiones calculi differentialis polynomials α₁(x) = 1, α₂(x) = x + 1, α₃(x) = x² + 4x + 1, etc. (see the facsimile). These polynomials are a shifted form of what are now called the Eulerian polynomials A_n(x).

Basic properties

For a given value of n > 0, the index m in A(n, m) can take values from 0 to n − 1. For fixed n there is a single permutation which has 0 ascents: (n, n − 1, n − 2, ..., 1). There is also a single permutation which has n − 1 ascents; this is the rising permutation (1, 2, 3, ..., n). Therefore A(n, 0) and A(n, n − 1) are 1 for all values of n.

Reversing a permutation with m ascents creates another permutation in which there are n − m − 1 ascents. Therefore A(n, m) = A(n, n − m − 1).

Values of A(n, m) can be calculated "by hand" for small values of n and m. For example

n	m	Permutations	A(n, m)
1	0	(1)	A(1,0) = 1
2	0	(2, 1)	A(2,0) = 1
	1	(1, 2)	A(2,1) = 1
3	0	(3, 2, 1)	A(3,0) = 1
	1	(1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2)	A(3,1) = 4
	2	(1, 2, 3)	A(3,2) = 1

For larger values of n, A(n, m) can be calculated using the recursive formula

${\displaystyle A(n,m)=(n-m)A(n-1,m-1)+(m+1)A(n-1,m).}$

For example

${\displaystyle A(4,1)=(4-1)A(3,0)+(1+1)A(3,1)=3\times 1+2\times 4=11.}$

Values of A(n, m) (sequence A008292 in the OEIS) for 0 ≤ n ≤ 9 are:

m n	0	1	2	3	4	5	6	7	8
1	1
2	1	1
3	1	4	1
4	1	11	11	1
5	1	26	66	26	1
6	1	57	302	302	57	1
7	1	120	1191	2416	1191	120	1
8	1	247	4293	15619	15619	4293	247	1
9	1	502	14608	88234	156190	88234	14608	502	1

The above triangular array is called the Euler triangle or Euler's triangle, and it shares some common characteristics with Pascal's triangle. The sum of row n is the factorial n!.

Explicit formula

An explicit formula for A(n, m) is

${\displaystyle A(n,m)=\sum _{k=0}^{m}(-1)^{k}{\binom {n+1}{k}}(m+1-k)^{n}.}$

One can see from this formula, as well as from the combinatorial interpretation, that ${\displaystyle A(n,n)=0}$ for ${\displaystyle n>0}$, so that ${\displaystyle A_{n}(t)}$ is a polynomial of degree ${\displaystyle n-1}$ for ${\displaystyle n>0}$.

Summation properties

It is clear from the combinatorial definition that the sum of the Eulerian numbers for a fixed value of n is the total number of permutations of the numbers 1 to n, so

${\displaystyle \sum _{m=0}^{n-1}A(n,m)=n!{\text{ for }}n\geq 1.}$

The alternating sum of the Eulerian numbers for a fixed value of n is related to the Bernoulli number B_n+1

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}A(n,m)={\frac {2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}}{\text{ for }}n\geq 1.}$

Other summation properties of the Eulerian numbers are:

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n-1}{m}}}=0{\text{ for }}n\geq 2,}$

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n}{m}}}=(n+1)B_{n}{\text{ for }}n\geq 2,}$

where B_n is the n^th Bernoulli number.

Identities

The Eulerian numbers are involved in the generating function for the sequence of n^th powers:

${\displaystyle \sum _{k=0}^{\infty }k^{n}x^{k}={\frac {\sum _{m=0}^{n-1}A(n,m)x^{m+1}}{(1-x)^{n+1}}}={\frac {x\cdot A_{n}(x)}{(1-x)^{n+1}}}}$

for ${\displaystyle n\geq 0}$. This assumes that 0⁰ = 0 and A(0,0) = 1 (since there is one permutation of no elements, and it has no ascents).

Worpitzky's identity[1] expresses xⁿ as the linear combination of Eulerian numbers with binomial coefficients:

${\displaystyle x^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {x+m}{n}}.}$

It follows from Worpitzky's identity that

${\displaystyle \sum _{k=1}^{N}k^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {N+1+m}{n+1}}.}$

Another interesting identity is

${\displaystyle {\frac {e}{1-ex}}=\sum _{n=0}^{\infty }{\frac {A_{n}(x)}{n!(1-x)^{n+1}}}.}$

The numerator on the right-hand side is the Eulerian polynomial.

For a fixed function ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {C} }$ which is integrable on ${\displaystyle (0,n)}$ we have the integral formula [2]

${\displaystyle \int _{0}^{1}\cdots \int _{0}^{1}f\left(\left\lfloor x_{1}+\cdots +x_{n}\right\rfloor \right)dx_{1}\cdots dx_{n}=\sum _{k}A(n,k){\frac {f(k)}{n!}}.}$

Eulerian numbers of the second kind

The permutations of the multiset {1, 1, 2, 2, ···, n, n} which have the property that for each k, all the numbers appearing between the two occurrences of k in the permutation are greater than k are counted by the double factorial number (2n−1)!!. The Eulerian number of the second kind, denoted ${\displaystyle \scriptstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle }$, counts the number of all such permutations that have exactly m ascents. For instance, for n = 3 there are 15 such permutations, 1 with no ascents, 8 with a single ascent, and 6 with two ascents:

332211,

221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,

112233, 122133, 112332, 123321, 133122, 122331.

The Eulerian numbers of the second kind satisfy the recurrence relation, that follows directly from the above definition:

${\displaystyle \left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle =(2n-m-1)\left\langle \!\!\left\langle {n-1 \atop m-1}\right\rangle \!\!\right\rangle +(m+1)\left\langle \!\!\left\langle {n-1 \atop m}\right\rangle \!\!\right\rangle ,}$

with initial condition for n = 0, expressed in Iverson bracket notation:

${\displaystyle \left\langle \!\!\left\langle {0 \atop m}\right\rangle \!\!\right\rangle =[m=0].}$

Correspondingly, the Eulerian polynomial of second kind, here denoted P_n (no standard notation exists for them) are

${\displaystyle P_{n}(x):=\sum _{m=0}^{n}\left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle x^{m}}$

and the above recurrence relations are translated into a recurrence relation for the sequence P_n(x):

${\displaystyle P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)}$

with initial condition

${\displaystyle P_{0}(x)=1.}$

The latter recurrence may be written in a somehow more compact form by means of an integrating factor:

${\displaystyle (x-1)^{-2n-2}P_{n+1}(x)=\left(x(1-x)^{-2n-1}P_{n}(x)\right)^{\prime }}$

so that the rational function

${\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}$

satisfies a simple autonomous recurrence:

${\displaystyle u_{n+1}=\left({\frac {x}{1-x}}u_{n}\right)^{\prime },\quad u_{0}=1,}$

whence one obtains the Eulerian polynomials as P_n(x) = (1−x)²ⁿ u_n(x), and the Eulerian numbers of the second kind as their coefficients.

Here are some values of the second order Eulerian numbers (sequence A008517 in the OEIS):

m n	0	1	2	3	4	5	6	7	8
1	1
2	1	2
3	1	8	6
4	1	22	58	24
5	1	52	328	444	120
6	1	114	1452	4400	3708	720
7	1	240	5610	32120	58140	33984	5040
8	1	494	19950	195800	644020	785304	341136	40320
9	1	1004	67260	1062500	5765500	12440064	11026296	3733920	362880

The sum of the n-th row, which is also the value P_n(1), is (2n − 1)!!.

References

• Eulerus, Leonardus [Leonhard Euler] (1755). Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Foundations of differential calculus, with applications to finite analysis and series]. Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
• Carlitz, L. (1959). "Eulerian Numbers and polynomials". Math. Mag. 32 (5): 247–260. doi:10.2307/3029225.
• Gould, H. W. (1978). "Evaluation of sums of convolved powers using Stirling and Eulerian Numbers". Fib. Quart. 16 (6): 488–497.
• Desarmenien, Jacques; Foata, Dominique (1992). "The signed Eulerian numbers". Discrete Math. 99 (1–3): 49–58. doi:10.1016/0012-365X(92)90364-L.
• Lesieur, Leonce; Nicolas, Jean-Louis (1992). "On the Eulerian Numbers M=max (A(n,k))". Europ. J. Combinat. 13 (5): 379–399. doi:10.1016/S0195-6698(05)80018-6.
• Butzer, P. L.; Hauss, M. (1993). "Eulerian numbers with fractional order parameters". Aequationes Mathematicae. 46: 119–142. doi:10.1007/bf01834003.
• Koutras, M.V. (1994). "Eulerian numbers associated with sequences of polynomials". Fib. Quart. 32 (1): 44.
• Graham; Knuth; Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley. pp. 267–272.
• Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (1999). "On certain summation problems and generalizations of Eulerian polynomials and numbers". Discrete Math. 204. pp. 237–247. doi:10.1016/S0012-365X(98)00379-3.
• Boyadzhiev, Khristo N. (2007). "Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials". arXiv:0710.1124.
• Petersen, T. Kyle (2015). Eulerian Numbers. Birkhäuser. pp. 3–18. doi:10.1007/978-1-4939-3091-3_1.

Citations

1. Worpitzky, J. (1883). "Studien über die Bernoullischen und Eulerschen Zahlen". Journal für die reine und angewandte Mathematik. 94: 203–232.
2. Exercise 6.65 in Concrete Mathematics by Graham, Knuth and Patashnik.

External links

• Eulerian Polynomials at OEIS Wiki.
• "Eulerian Numbers". MathPages.com.
• Weisstein, Eric W. "Eulerian Number". MathWorld.
• Weisstein, Eric W. "Euler's Number Triangle". MathWorld.
• Weisstein, Eric W. "Worpitzky's Identity". MathWorld.
• Weisstein, Eric W. "Second-Order Eulerian Triangle". MathWorld.
• Euler-matrix (generalized rowindexes, divergent summation)