Eulerian number explained

In combinatorics, the Eulerian number $A(n,k)$ is the number of permutations of the numbers 1 to $n$ in which exactly $k$ elements are greater than the previous element (permutations with $k$ "ascents").

Leonhard Euler investigated them and associated polynomials in his 1755 book Institutiones calculi differentialis.

Other notations for $A(n,k)$ are $E(n,k)$ and

style \left\langle {n \atop k} \right\rangle .

Definition

The Eulerian polynomials

A _{n(t)} are defined by the exponential generating function\sum ^{inf ty} _{n =0} A _{n} (t) (x ^{n})/(n!) = (t -1)/(t - e ^{(t-1)x}) . The Eulerian numbers A(n,k) may be defined as the coefficients of the Eulerian polynomials:A _{n} (t) = \sum ^{n} _{k =0} A(n,k)t ^{k.}

An explicit formula for $A(n,k)$ is^[1]

A(n,k) = \sum ^{k} _{i =0} ( -1 ) ^{i} \binom{n +1 }{i} (k +1- i) ^{n.}

Basic properties

• For fixed $n$ there is a single permutation which has 0 ascents: $(n,\; n-1,\; n-2,\; \backslash ldots,\; 1)$. Indeed, as

{\tbinom n 0 } =1 for all n , $A(n,\; 0)\; =\; 1$. This formally includes the empty collection of numbers, $n=0$. And so $A\_0(t)=A\_1(t)=1$.

• For $k=1$ the explicit formula implies $A(n,1)=2^n-(n+1)$, a sequence in

n that reads $0,\; 0,\; 1,\; 4,\; 11,\; 26,\; 57,\; \backslash dots$.

• Fully reversing a permutation with $k$ ascents creates another permutation in which there are $n-k-1$ ascents. Therefore $A(n,\; k)\; =\; A(n,\; n-k-1)$. So there is also a single permutation which has $n-1$ ascents, namely the rising permutation $(1,\; 2,\; \backslash ldots,\; n)$. So also $A(n,\; n-1)$ equals

1 .

• A lavish upper bound is $A(n,\; k)\; \backslash le\; (k+1)^n\backslash cdot(n+2)^k$. Between the bounds just discussed, the value exceeds

1 .

• For $k\backslash ge\; n\; >\; 0$, the values are formally zero, meaning many sums over $k$ can be written with an upper index only up to $n-1$. It also means that the polynomials

A _{n} (t) are really of degree $n-1$ for $n>0$.

A tabulation of the numbers in a triangular array is called the Euler triangle or Euler's triangle. It shares some common characteristics with Pascal's triangle. Values of $A(n,\; k)$ for $0\; \backslash le\; n\; \backslash le\; 9$ are:

	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

Computation

For larger values of $n$, $A(n,k)$ can also be calculated using the recursive formula

A(n,k) = (n - k)A(n -1 ,k -1 ) + (k +1 )A(n -1 ,k). This formula can be motivated from the combinatorial definition and thus serves as a natural starting point for the theory.

For small values of $n$ and $k$, the values of $A(n,k)$ can be calculated by hand. For example

n	k	Permutations	A(n, k)
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) and (3, 1, 2)	A(3,1) = 4
	2	(1, 2, 3)	A(3,2) = 1

Applying the recurrence to one example, we may find

A( 4 , 1 ) = ( 4-1 )A( 3 , 0 ) + ( 1+1 )A( 3 , 1 ) =3 ⋅ 1 + 2 ⋅ 4 = 11 .

Likewise, the Eulerian polynomials can be computed by the recurrence

A _{0} (t) = 1 , A _{n} (t) = A _{n-1} '(t) ⋅ t( 1- t) + A _{n-1} (t) ⋅ ( 1+ (n -1 )t), for n > 1 . The second formula can be cast into an inductive form, A _{n} (t) = \sum ^{n -1} _{k =0} \binom{n}{k} A _{k} (t) ⋅ (t -1 ) ^{n-1-k} , for n > 1 .

Identities

For any property partitioning a finite set into finitely many smaller sets, the sum of the cardinalities of the smaller sets equals the cardinality of the bigger set. The Eulerian numbers partition the permutations of

n elements, so their sum equals the factorial n! . I.e.\sum ^{n -1} _{k =0} A(n,k) = n!, for n > 0 . as well as A( 0 , 0 ) =0 ! . To avoid conflict with the empty sum convention, it is convenient to simply state the theorems for n> 0 only.

Much more generally, for a fixed function

f\colon R → C integrable on the interval ( 0 , n) ^[2] \sum ^{n -1} _{k =0} A(n, k) f(k) = n!\int ^{1} _{0} … \int ^{1} _{0} f\left(\left\lfloor x _{1} + … + x _{n\right\rfloor\right)} { d}x _{1} … { d}x _{n} Worpitzky's identity^[3] expresses $x^n$ as the linear combination of Eulerian numbers with binomial coefficients:\sum ^{n -1} _{k =0} A(n,k)\binom{x + k}{n} = x ^{n.} From it, it follows that \sum ^{m} _{k =1} k ^{n -1} _{k =0} A(n,k) \binom{m + k +1 }{n +1 }.

Formulas involving alternating sums

The alternating sum of the Eulerian numbers for a fixed value of $n$ is related to the Bernoulli number $B\_$

\sum ^{n -1} _{k =0} ( -1 ) ^{k} A(n,k) = 2 ^{n+1} ( 2 ^{n+1} -1 ) (B _{n+1})/(n +1) , for n > 0 . Furthermore,\sum ^{n -1} _{k =0} ( -1 ) ^{k} (A(n,k))/(\binom{n -1) {k}} =0 , for n > 1 and\sum ^{n -1} _{k =0} ( -1 ) ^{k} (A(n,k))/(\binom{n) {k}} = (n +1 )B _{n} , for n > 1

Formulas involving the polynomials

The symmetry property implies:

A _{n(t)} = t ^{n-1} A ^{-1} _{n(t} ) The Eulerian numbers are involved in the generating function for the sequence of n^th powers:\sum ^{inf ty} _{i =1} i ^{n} x ^{i} = (1)/(( 1- x) ^{n+1}) \sum ^{n} _{k =0} A(n,k)x ^{k+1} = (x)/(( 1- x) ^{n+1}) A _{n(x)} An explicit expression for Eulerian polynomials is ^[4] A _{n(t)} = \sum ^{n} _{k =0} \left\{ {n \atop k} \right\} k! (t -1 ) ^{n-k}

Where $\backslash left\backslash$ is the Stirling numbers of the second kind.

Eulerian numbers of the second order

The permutations of the multiset $\backslash$ 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

\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 order satisfy the recurrence relation, that follows directly from the above definition:

\left\langle \left\langle {n \atop k} \right\rangle \right\rangle = ( 2 n - k -1 ) \left\langle \left\langle {n -1 \atop k -1 } \right\rangle \right\rangle + (k +1 ) \left\langle \left\langle {n -1 \atop k} \right\rangle \right\rangle, with initial condition for n = 0, expressed in Iverson bracket notation:\left\langle \left\langle { 0 \atop k} \right\rangle \right\rangle = [k =0 ]. Correspondingly, the Eulerian polynomial of second order, here denoted P_n (no standard notation exists for them) areP _{n(x)} : = \sum ^{n} _{k =0} \left\langle \left\langle {n \atop k} \right\rangle \right\rangle x ^{k} and the above recurrence relations are translated into a recurrence relation for the sequence P_n(x):P _{n+1} (x) = ( 2 nx +1 ) P _{n(x)} - x(x -1 ) P ^{\prime(x)} _{n} with initial condition P _{0(x)} = 1 . . The latter recurrence may be written in a somewhat 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 functionu _{n(x)} : = (x -1 ) ^{-2n} P _{n} (x) satisfies a simple autonomous recurrence:u _{n+1} = \left( (x)/(1- x) u _{n} \right) ^{\prime,} u _{0=1} Whence one obtains the Eulerian polynomials of second order as $P\_n(x)\; =\; (1-x)^\; u\_n(x)$, and the Eulerian numbers of second order as their coefficients.

The following table displays the first few second-order Eulerian numbers:

	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 $(2n-1)!!$.

Indexing the second-order Eulerian numbers comes in three flavors:

• following Riordan and Comtet,
• following Graham, Knuth, and Patashnik,
• , 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.
• L. . Carlitz. Eulerian Numbers and polynomials . 1959. Math. Mag.. 32 . 5 . 247–260. 10.2307/3029225. 3029225.
• H. W. . Gould. Evaluation of sums of convolved powers using Stirling and Eulerian Numbers. 1978. Fib. Quart.. 16 . 488–497. 6.
• Jacques . Desarmenien . Dominique . Foata . The signed Eulerian numbers. Discrete Math.. 1992. 99 . 1–3. 49–58. 10.1016/0012-365X(92)90364-L. free.
• 1992. Europ. J. Combinat. . 13 . 379–399. 5. On the Eulerian Numbers M=max (A(n,k)). Leonce . Lesieur . Jean-Louis . Nicolas. 10.1016/S0195-6698(05)80018-6. free.
• P. L. . Butzer . M. . Hauss. Eulerian numbers with fractional order parameters. . 1993 . 46. 1–2 . 119–142. 10.1007/bf01834003. 121868847 .
• M.V. . Koutras. Eulerian numbers associated with sequences of polynomials. Fib. Quart.. 1994. 44. 32. 1.
• Book: Graham. Knuth. Patashnik. 1994. Concrete Mathematics

  A Foundation for Computer Science

  . 2nd. Addison-Wesley. 267–272.

• Leetsch C. . Hsu . Leetsch C. Hsu . Peter . Jau-Shyong Shiue. On certain summation problems and generalizations of Eulerian polynomials and numbers. Discrete Math. . 204 . 1999 . 1–3 . 10.1016/S0012-365X(98)00379-3. 237–247. free .
• 0710.1124 . Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials. 2007. Khristo N. . Boyadzhiev. math.CA.
• Book: T. Kyle. Petersen. 2015. Eulerian Numbers . Eulerian numbers . Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. 10.1007/978-1-4939-3091-3_1. 3–18. 978-1-4939-3090-6.

External links

• Eulerian Polynomials at OEIS Wiki.
  • • • • • Euler-matrix (generalized rowindexes, divergent summation)

Notes and References

1. (L. Comtet 1974, p. 243)
2. Exercise 6.65 in Concrete Mathematics by Graham, Knuth and Patashnik.
3. Worpitzky . J. . Studien über die Bernoullischen und Eulerschen Zahlen . Journal für die reine und angewandte Mathematik . 1883 . 94 . 203–232 .
4. Qi . Feng . Guo . Bai-Ni . 2017-08-01 . Explicit formulas and recurrence relations for higher order Eulerian polynomials . Indagationes Mathematicae . 28 . 4 . 884–891 . 10.1016/j.indag.2017.06.010 . 0019-3577. free .