Eulerian number

From Wikipedia, the free encyclopedia

This page discusses a topic in combinatorics. For "Euler numbers" in number theory see Euler number.

In combinatorics the Eulerian number E(n, m), or

$\left \langle {n\atop m} \right \rangle,$

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").

1 Basic properties
2 Closed-form expression
3 Summation properties
4 Identities
5 References

[edit] Basic properties

For a given value of n, the index m in E(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 E(n, 0) and E(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 E(n, m) = E(n, n − m − 1).

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

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

For larger values of n, E(n, m) can be calculated using the recursion formula

E (n, m) = (n - m) E (n - 1, m - 1) + (m + 1) E (n - 1, m).

For example

$E(4,1)=(4-1)E(3,0) + (1+1)E(3,1)=3 \times 1 + 2 \times 4 = 11.$

Values of E(n, m) up to n = 9 are (sequence A008292 in OEIS):

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 arrangement is called the Euler triangle or Euler's triangle, and it shares some common characteristics with Pascal's triangle.

[edit] Closed-form expression

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

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

[edit] 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}E(n,m)=n!.$