Eulerian number

Template:Use American English Template:Short description 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.

File:EulerianPolynomialsByEuler1755.png

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.

Other notations for $A(n,k)$ are $E(n,k)$ and $⟨\genfrac{}{}{0ex}{}{n}{k}⟩$.

Definition

The Eulerian polynomials $A_n(t)$ are defined by the exponential generating function

$\sum _{n=0}^{\mathrm{\infty }}{A}_n(t)\frac{x^n}{n!}=\frac{t-1}{t-e^{(t-1)x}}={(1-\frac{e^{(t-1)x}-1}{t-1})}^{-1}.$

The Eulerian numbers $A(n,k)$ may be defined as the coefficients of the Eulerian polynomials:

$A_n(t)=\sum _{k=0}^{n}A(n,k)t^k.$

An explicit formula for $A(n,k)$ is

A plot of the Eulerian numbers with the second argument fixed to 5.

A plot of the Eulerian numbers with the second argument fixed to 5.

$A(n,k)=\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{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,\dots ,1)$. Indeed, as $(\genfrac{}{}{0ex}{}{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,\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,\dots ,n)$. So also $A(n,n-1)$ equals $1$.
• A lavish upper bound is $A(n,k)\le (k+1{)}^n\cdot (n+2{)}^k$. Between the bounds just discussed, the value exceeds $1$.
• For $k\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)$ (sequence A008292 in the OEIS) for $0\le n\le 9$ are:

Template:Diagonal split header	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\cdot 1+2\cdot 4=11.$

Likewise, the Eulerian polynomials can be computed by the recurrence

$A_0(t)=1,$

$A_n(t)=A_{n^{\prime }-1}(t)\cdot t(1-t)+A_{n-1}(t)\cdot (1+(n-1)t),\text{ for }n>1.$

The second formula can be cast into an inductive form,

$A_n(t)=\sum _{k=0}^{n-1}(\genfrac{}{}{0ex}{}{n}{k})A_k(t)\cdot (t-1{)}^{n-1-k},\text{ 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 _{k=0}^{n-1}A(n,k)=n!,\text{ 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:\mathbb{ℝ}\to \mathbb{ℂ}$ integrable on the interval $(0,n)$

$\sum _{k=0}^{n-1}A(n,k)f(k)=n!\underset{0}{\overset{1}{\int }}\cdots \underset{0}{\overset{1}{\int }}f\left(\lfloor x_1+\cdots +x_n\rfloor \right)\mathrm{d}{x}_1\cdots \mathrm{d}{x}_n$

Worpitzky's identity expresses $x^n$ as the linear combination of Eulerian numbers with binomial coefficients:

$\sum _{k=0}^{n-1}A(n,k)(\genfrac{}{}{0ex}{}{x+k}{n})=x^n.$

From it, it follows that

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

$\sum _{k=0}^{n-1}(-1{)}^{k}A(n,k)=2^{n+1}(2^{n+1}-1)\frac{B_{n+1}}{n+1},\text{ for }n>0.$

Furthermore,

$\sum _{k=0}^{n-1}(-1{)}^k\frac{A(n,k)}{(\genfrac{}{}{0ex}{}{n-1}{k})}=0,\text{ for }n>1$

and

$\sum _{k=0}^{n-1}(-1{)}^k\frac{A(n,k)}{(\genfrac{}{}{0ex}{}{n}{k})}=(n+1)B_n,\text{ for }n>1$

Formulas involving the polynomials

The symmetry property implies:

$A_n(t)=t^{n-1}{A}_n(t^{-1})$

The Eulerian numbers are involved in the generating function for the sequence of n^th powers:

$\sum _{i=1}^{\mathrm{\infty }}{i}^n{x}^i=\frac{1}{(1-x{)}^{n+1}}\sum _{k=0}^{n}A(n,k)x^{k+1}=\frac{x}{(1-x{)}^{n+1}}{A}_n(x)$

An explicit expression for Eulerian polynomials is

$$A_n(t)=\sum _{k=0}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}k!(t-1{)}^{n-k}$$

where $\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$ is the Stirling number of the second kind.

Eulerian numbers of the second order

The permutations of the multiset $\{1,1,2,2,\dots ,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 $⟨⟨\genfrac{}{}{0ex}{}{n}{m}⟩⟩$, 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:

$⟨⟨\genfrac{}{}{0ex}{}{n}{k}⟩⟩=(2n-k-1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{k-1}⟩⟩+(k+1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{k}⟩⟩,$

with initial condition for n = 0, expressed in Iverson bracket notation:

$⟨⟨\genfrac{}{}{0ex}{}{0}{k}⟩⟩=[k=0].$

Correspondingly, the Eulerian polynomial of second order, here denoted P_n (no standard notation exists for them) are

$P_n(x):=\sum _{k=0}^n⟨⟨\genfrac{}{}{0ex}{}{n}{k}⟩⟩x^k$

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 somewhat more compact form by means of an integrating factor:

$(x-1{)}^{-2n-2}{P}_{n+1}(x)={(x(1-x{)}^{-2n-1}{P}_n(x))}^{\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 },u_0=1$

Whence one obtains the Eulerian polynomials of second order as $P_n(x)=(1-x{)}^{2n}{u}_n(x)$, and the Eulerian numbers of second order as their coefficients.

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

Template:Diagonal split header	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:

• (sequence A008517 in the OEIS) following Riordan and Comtet,
• (sequence A201637 in the OEIS) following Graham, Knuth, and Patashnik,
• (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.

External links

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