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:

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

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 - \mathrm{e}^{(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 \ge 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 \ge 1.$

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

History

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; this is the falling permutation (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

$A(n,m)=(n-m)A(n-1,m-1) + (m+1)A(n-1,m).$

For example

$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 OEIS) for 0 ≤ n ≤ 9 are:

n \ m	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!.

Closed-form expression

A closed-form expression for A(n, m) is

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

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

$\sum_{m=0}^{n-1}A(n,m)=n! \text{ for }n \ge 1.$

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

$\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 \ge 1.$

Other summation properties of the Eulerian numbers are:

$\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n-1}{m}}=0 \text{ for }n \ge 2,$

$\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n}{m}}=(n+1)B_{n} \text{ for }n \ge 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,

$\sum_{k=0}^{\infty}k^n x^k = \frac{\sum_{m=0}^{n-1}A(n,m)x^{m+1}}{(1-x)^{n+1}}$

for $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 expresses xⁿ as the linear combination of Eulerian numbers with binomial coefficients:

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

It follows from Worpitzky's identity that

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

Another interesting identity is

$\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.

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 $\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:

$\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:

$\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

$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):

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

with initial condition

$P_0(x) = 1.$

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

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

so that the rational function

$u_n(x) := (x-1)^{-2n} P_{n}(x)$

satisfies a simple autonomous recurrence:

$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 OEIS):

n \ m	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 then (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.
• Graham, Knuth, Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science, Second Edition. Addison-Wesley, pp. 267–272.
• Butzer, P. L.; Hauss, M. (1993). "Eulerian numbers with fractional order parameters". Aequationes Mathematicae 46: 119–142. doi:10.1007/bf01834003.
• T. K. Petersen (2015). Eulerian Numbers Birkhaüser. http://www.springer.com/us/book/9781493930906

External links

• Eulerian Polynomials at OEIS Wiki.
• "Eulerian Numbers" at 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)