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.

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 ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$.

Definition

The Eulerian polynomials are defined by the exponential generating function

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

The Eulerian numbers may be defined as the coefficients of the Eulerian polynomials:

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

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

${\displaystyle A(n,k)=\sum _{i=0}^{k}(-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, ..., 1). Indeed, as ${\displaystyle {\tbinom {n}{0))=1}$ for all ${\displaystyle n}$, ${\displaystyle A(n,0)=1}$. This formally includes the empty collection of numbers, ${\displaystyle n=0}$. And so ${\displaystyle A_{0}(t)=A_{1}(t)=1}$.
• For ${\displaystyle k=1}$ the explicit formula implies ${\displaystyle A(n,1)=2^{n}-(n+1)}$, a sequence in ${\displaystyle n}$ that reads ${\displaystyle 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, 3, ..., n). So also A(n, n − 1) equals ${\displaystyle 1}$.
• A lavish upper bound is ${\displaystyle A(n,k)\leq (k+1)^{n}\cdot (n+2)^{k))$. Between the bounds just discussed, the value exceeds ${\displaystyle 1}$.
• For ${\displaystyle k\geq n>0}$, the values are formally zero, meaning many sums over ${\displaystyle k}$ can be written with an upper index only up to ${\displaystyle n-1}$. It also means that the polynomials ${\displaystyle A_{n}(t)}$ are really of degree ${\displaystyle n-1}$ for ${\displaystyle 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 ≤ n ≤ 9 are:

m n	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

${\displaystyle 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

${\displaystyle 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

${\displaystyle A_{0}(t)=1,}$

${\displaystyle A_{n}(t)=A_{n-1}'(t)\cdot t\,(1-t)+A_{n-1}(t)\cdot (1+(n-1)\,t),\quad n\geq 1.}$

The second formula can be cast into an inductive form,

${\displaystyle A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k))A_{k}(t)\cdot (t-1)^{n-1-k},\quad n\geq 1.}$

The following is a python implementation.

import math  # python 3.8

def Ank(n, k) -> int:
    """
    Compute A(n, k) using the explicit formula.
    """
    def summand(i):
        return (-1) ** i * math.comb(n + 1, i) * (k + 1 - i) ** n
    return sum(map(summand, range(k + 1)))

def Anks(n) -> list:
    """
    Coefficient list for the n'th polynomial A_n(t).
    """
    return [1] if n == 0 else [Ank(n, k) for k in range(n)]

def eval_polynomial(coeffs, t):
    """
    Polynomial evaluation function.
    """
    return sum(c * t ** k for k, c in enumerate(coeffs))

def An(n, t: float) -> float:
    """
    Polynomial A_n(t).
    """
    return eval_polynomial(Anks(n), t)

# Print the first few polynomials
sup = lambda n: str(n).translate(str.maketrans("0123456789", "⁰¹²³⁴⁵⁶⁷⁸⁹"))
sub = lambda n: str(n).translate(str.maketrans("0123456789", "₀₁₂₃₄₅₆₇₈₉"))

NUM = 8
for n in range(NUM):
    print(f"A{sub(n)}(t) = " + " + ".join(f"{ank} t{sup(k)}" for k, ank in enumerate(Anks(n))))
    # E.g. A₇(t) = 1 t⁰ + 120 t¹ + 1191 t² + 2416 t³ + 1191 t⁴ + 120 t⁵ + 1 t⁶

    # Sanity checks
    assert Ank(n, 1) == 2 ** n - (n + 1)
    assert n == 0 or An(n, 1) == math.factorial(n)  # Cardinality check
    alternating_sum: float = sum((-1)**k * Ank(n, k) / math.comb(n - 1, k) for k in range(n))
    assert n < 2 or abs(alternating_sum) < 1e-13

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 ${\displaystyle n}$ elements, so their sum equals the factorial ${\displaystyle n!}$. I.e.

${\displaystyle \sum _{k=0}^{n-1}A(n,k)=n!{\text{ for ))n>0.}$

as well as ${\displaystyle A(0,0)=0!}$. To avoid conflict with the empty sum convention, it is convenient to simply state the theorems for ${\displaystyle n>0}$ only.

Much more generally, for a fixed function ${\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {C} }$ integrable on the interval ${\displaystyle (0,n)}$^[2]

${\displaystyle \sum _{k}^{n-1}A(n,k)\,f(k)=n!\int _{0}^{1}\cdots \int _{0}^{1}f\left(\left\lfloor x_{1}+\cdots +x_{n}\right\rfloor \right){\mathrm {d} }x_{1}\cdots {\mathrm {d} }x_{n))$

Worpitzky's identity^[3] expresses xⁿ as the linear combination of Eulerian numbers with binomial coefficients:

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

From it, it follows that

${\displaystyle \sum _{k=1}^{m}k^{n}=\sum _{k=0}^{n-1}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_n+1

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

Furthermore,

${\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k))}=0{\text{ for ))n\geq 2,}$

and

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

Formulas involving the polynomials

The symmetry property implies:

${\displaystyle 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:

${\displaystyle \sum _{i=1}^{\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)}$

It also holds that,

${\displaystyle {\frac {\mathrm {e} }{1-\mathrm {e} \,x))=\sum _{n=0}^{\infty }{\frac {1}{n!(1-x)^{n+1))}A_{n}(x).}$

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 ${\displaystyle \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:

${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-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:

${\displaystyle \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) are

${\displaystyle P_{n}(x):=\sum _{k=0}^{n}\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):

${\displaystyle P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)}$

with initial condition ${\displaystyle P_{0}(x)=1.}$. The latter recurrence may be written in a somewhat more compact form by means of an integrating factor:

${\displaystyle (x-1)^{-2n-2}P_{n+1}(x)=\left(x\,(1-x)^{-2n-1}P_{n}(x)\right)^{\prime ))$

so that the rational function

${\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}$

satisfies a simple autonomous recurrence:

${\displaystyle u_{n+1}=\left({\frac {x}{1-x))u_{n}\right)^{\prime },\quad 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:

k n	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.