In combinatorics, the Eulerian numberA(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:
The Eulerian polynomials are defined by the exponential generating function
The Eulerian polynomials can be computed by the recurrence
An equivalent way to write this definition is to set the Eulerian polynomials inductively by
Other notations for A(n, m) are E(n, m) and .
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, in his book Institutiones calculi differentialis, Leonhard Euler investigated polynomials α1(x) = 1, α2(x) = x + 1, α3(x) = x2 + 4x + 1, etc. (see the facsimile). These polynomials are a shifted form of what are now called the Eulerian polynomials An(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
For example
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 factorialn!.
One can see from this formula, as well as from the combinatorial interpretation, that for , so that is a polynomial of degree for .
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
The numerator on the right-hand side is the Eulerian polynomial.
For a fixed function which is integrable on we have the integral formula [3]
Eulerian numbers of the second order
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 order, denoted , 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:
The Eulerian numbers of the second order satisfy the recurrence relation, that follows directly from the above definition:
with initial condition for n = 0, expressed in Iverson bracket notation:
Correspondingly, the Eulerian polynomial of second order, here denoted Pn (no standard notation exists for them) are
and the above recurrence relations are translated into a recurrence relation for the sequence Pn(x):
with initial condition
The latter recurrence may be written in a somehow more compact form by means of an integrating factor:
so that the rational function
satisfies a simple autonomous recurrence:
whence one obtains the Eulerian polynomials of second order as Pn(x) = (1−x)2nun(x), and the Eulerian numbers of second order as their coefficients.
Here are some values of the second order Eulerian numbers:
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 Pn(1), is (2n − 1)!!.
Indexing the second-order Eulerian numbers comes in three flavors: (sequence A008517 in the OEIS) following Riordan and Comtet, (sequence A201637 in the OEIS) following Graham, Knuth, and Patashnik and (sequence A340556 in the OEIS), extending the definition of Gessel and Stanley.
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.