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

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

Other notations for ${\textstyle A(n,k)}$ are ${\textstyle 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-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 ${\textstyle 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 ${\textstyle n}$ there is a single permutation which has 0 ascents: ${\textstyle (n,n-1,n-2,\ldots ,1)}$. Indeed, as ${\displaystyle {\tbinom {n}{0))=1}$ for all ${\displaystyle n}$, ${\textstyle A(n,0)=1}$. This formally includes the empty collection of numbers, ${\textstyle n=0}$. And so ${\textstyle A_{0}(t)=A_{1}(t)=1}$.
• For ${\textstyle k=1}$ the explicit formula implies ${\textstyle A(n,1)=2^{n}-(n+1)}$, a sequence in ${\displaystyle n}$ that reads ${\textstyle 0,0,1,4,11,26,57,\dots }$.
• Fully reversing a permutation with ${\textstyle k}$ ascents creates another permutation in which there are ${\textstyle n-k-1}$ ascents. Therefore ${\textstyle A(n,k)=A(n,n-k-1)}$. So there is also a single permutation which has ${\textstyle n-1}$ ascents, namely the rising permutation ${\textstyle (1,2,\ldots ,n)}$. So also ${\textstyle A(n,n-1)}$ equals ${\displaystyle 1}$.
• A lavish upper bound is ${\textstyle A(n,k)\leq (k+1)^{n}\cdot (n+2)^{k))$. Between the bounds just discussed, the value exceeds ${\displaystyle 1}$.
• For ${\textstyle k\geq n>0}$, the values are formally zero, meaning many sums over ${\textstyle k}$ can be written with an upper index only up to ${\textstyle n-1}$. It also means that the polynomials ${\displaystyle A_{n}(t)}$ are really of degree ${\textstyle n-1}$ for ${\textstyle 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 ${\textstyle A(n,k)}$ (sequence A008292 in the OEIS) for ${\textstyle 0\leq n\leq 9}$ are:

k 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 ${\textstyle n}$, ${\textstyle 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 ${\textstyle n}$ and ${\textstyle k}$, the values of ${\textstyle 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),{\text{ for ))n>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},{\text{ for ))n>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=0}^{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 ${\textstyle x^{n))$ 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 ${\textstyle n}$ is related to the Bernoulli number ${\textstyle B_{n+1))$

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

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

and

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

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 {e}{1-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 ${\textstyle \{1,1,2,2,\ldots ,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 ${\textstyle (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 ${\textstyle 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:

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 ${\textstyle P_{n}(1)}$, is ${\textstyle (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.