Eulerian number

:"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\; \{natop\; m\}\; ight\; angle,$

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

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

:

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\; imes\; 1\; +\; 2\; imes\; 4\; =\; 11.$

Values of "E"("n", "m") up to "n" = 9 are OEIS|id=A008292:

:

The above arrangement is called the Euler triangle or Euler's triangle, and it shares some common characteristics with Pascal's triangle.

Closed-form expression

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

:

ummation 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!.$

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\}E(n,m)=frac\{2^\{n+1\}(2^\{n+1\}-1)B\_\{n+1\{n+1\}.$

Other summation properties of the Eulerian numbers are:

:

:

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-1\}E(n,m)x^\{m+1\{(1-x)^\{n+1.$

The Eulerian numbers are also involved in Worpitzky's identity, which expresses "x"^"n" as the sum of generalised binomial coefficients

:

References

*MathWorld|title=Eulerian Number|urlname=EulerianNumber
*MathWorld|title=Worpitzky's Identity|urlname=WorpitzkysIdentity
* [http://www.mathpages.com/home/kmath012/kmath012.htm Eulerian Numbers] at "MathPages"
* [http://www.cecm.sfu.ca/organics/papers/buhler/paper/html/node5.html Counting Periodic Juggling Patterns] by Joe Buhler, David Eisenbud, Ron Graham, Colin Wright
*Graham, Knuth, Patashnik (1994). "Concrete Mathematics: A Foundation for Computer Science", Second Edition. Addison-Wesley, pp. 267–272.