Eulerian number

This article is about a topic in combinatorics. For "Euler numbers" in number theory, see Euler 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}(x)=\sum _{m=0}^{n}A(n,m)\ x^{n-m}.$

This polynomial appears as the numerator in an expression for the generating function of the sequence $1^{n},\ 2^{n},\ 3^{n},\ \dots$.

Other notations for A(n, m) are E(n, m) and $\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 recursion 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 the OEIS) for 0 ≤ n ≤ 9 are:

n \ m	0	1	2	3	4	5	6	7	8
0	1
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)^{k}{\binom {n+1}{k}}(m+1-k)^{n}.$

Summation properties

It is clear from the combinatoric 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!.$

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

Other summation properties of the Eulerian numbers are:

$\sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n-1}{m}}}=0,$

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

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=1}^{\infty }k^{n}x^{k}={\frac {\sum _{m=0}^{n}A(n,m)x^{m+1}}{(1-x)^{n+1}}}.$

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

Another interesting identity is given by the following manipulation:

$e^{k}=\sum _{n=0}^{\infty }{\frac {k^{n}}{n!}}$

$(x^{k})(e^{k})=\sum _{n=0}^{\infty }{\frac {(x^{k})(k^{n})}{n!}}$

$\sum _{k=1}^{\infty }(x^{k})(e^{k})=\sum _{k=1}^{\infty }\sum _{n=0}^{\infty }{\frac {(x^{k})(k^{n})}{n!}}$

So for $0\leq x<{\frac {1}{e}}$ we have that the terms on the right side are positive, so we may switch the sum. The terms on the left make a geometric series, and we know that converges. After all of that, we use the above identity to finish the manipulation:

$\sum _{k=1}^{\infty }(xe)^{k}=\sum _{k=1}^{\infty }\sum _{n=0}^{\infty }{\frac {(x^{k})(k^{n})}{n!}}$

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

Finally, for $0\leq x<{\frac {1}{e}}$ we get

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

Notice that the sum on the right-hand side is the sum of the Eulerian polynomials shown at the top of this page.

Eulerian numbers of the second kind

The permutations of the multiset $\{1,1,2,2,\cdots ,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 $\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,\;332211.$

The Eulerian numbers of the second kind $\left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle$ 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 _{n=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 the OEIS):

n \ m	0	1	2	3	4	5	6	7	8
0	1
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

• Leonardus Eulerus (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: Michaelis.
• Graham, Knuth, Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science, Second Edition. Addison-Wesley, pp. 267–272.

External links

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