# Eulerian number

In combinatorics, the Eulerian number A(n, k){\textstyle A(n, k)} is the number of permutations of the numbers 1 to n{\textstyle n} in which exactly k{\textstyle k} elements are greater than the previous element (permutations with k{\textstyle k} "ascents").
Leonhard Euler investigated them and associated polynomials in his 1755 book Institutiones calculi differentialis.
Other notations for A(n, k){\textstyle A(n, k)} are E(n, k){\textstyle E(n, k)} and $\textstyle \left\langle {n \atop k}\right\rangle$.

## Definition

The Eulerian polynomials $A_{n}(t)$ are defined by the exponential generating function
    $\sum _{n=0}^{\infty }A_{n}(t)\,{\frac {x^{n}}{n!}}={\frac {t-1}{t-e^{(t-1)\,x}}}=\left(1-{\frac {e^{(t-1)x}-1}{t-1}}\right)^{-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){\textstyle A(n, k)} is
    A plot of the Eulerian numbers with the second argument fixed to 5.$A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.$

## Basic properties

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

## Computation

For larger values of n{\textstyle n}, A(n, k){\textstyle 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{\textstyle n} and k{\textstyle k}, the values of A(n, k){\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
    $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-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}{\binom {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\colon \mathbb {R} \rightarrow \mathbb {C}$ integrable on the interval $(0,n)$
    $\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 expresses x$^n${\textstyle x^{n}} as the linear combination of Eulerian numbers with binomial coefficients:
    $\sum _{k=0}^{n-1}A(n,k){\binom {x+k}{n}}=x^{n}.$
From it, it follows that
    $\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{\textstyle n} is related to the Bernoulli number B$_{n+1}${\textstyle 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)}{\binom {n-1}{k}}}=0,{\text{ for }}n>1$
and
    $\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:
    $A_{n}(t)=t^{n-1}A_{n}(t^{-1})$
The Eulerian numbers are involved in the generating function for the sequence of nth powers:
    $\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)$
An explicit expression for Eulerian polynomials is
$A_{n}(t)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}k!(t-1)^{n-k}$
where {n/k}{\textstyle \left\{{n \atop 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, …, n, n}{\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 (2n−1)!!{\textstyle (2n-1)!!}. The Eulerian number of the second order, denoted ⟨⟨ n/m ⟩⟩{\textstyle \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 =(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:
    $\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
    $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):
    $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)=\left(x\,(1-x)^{-2n-1}P_{n}(x)\right)^{\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 },\quad u_{0}=1$
Whence one obtains the Eulerian polynomials of second order as P$_n$(x)=(1−x)$^{2n}$u$_n$(x){\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:
    kn  0 1 2 3 4 5 6 7 8 0 1 1 1 2 12 3 186 4 1225824 5 152328444120 6 1114145244003708720 7 124056103212058140339845040 8 14941995019580064402078530434113640320 9 11004672601062500576550012440064110262963733920362880
The sum of the n-th row, which is also the value P$_n$(1){\textstyle P_{n}(1)}, is (2n−1)!!{\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.