Incombinatorics, theEulerian number$A(n,k)$ is the number ofpermutations 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 associatedpolynomials in his 1755 bookInstitutiones calculi differentialis. He first studied them in 1749 (though first printed in 1768).^[1]

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

TheEulerian polynomials${\displaystyle A_n(t)}$ are defined by the exponential generating function

${\displaystyle \sum _{n=0}^{\mathrm{\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}.}$

TheEulerian numbers${\displaystyle A(n,k)}$ may also 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^[2]

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

• For fixed$n$ there is a single permutation which has 0 ascents:$(n,n-1,n-2,\dots ,1)$. Indeed, as${\displaystyle (\genfrac{}{}{0ex}{}{n}{0})=1}$ for all${\displaystyle 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${\displaystyle 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${\displaystyle 1}$.
• Since a permutation of the numbers${\displaystyle 1}$ to${\displaystyle n}$ which has${\displaystyle k}$ ascents must have${\displaystyle n-1-k}$ descents, the symmetry$A(n,k)=A(n,n-k-1)$ shows that$A(n,k)$ also counts the number of permutations with${\displaystyle k}$descents.
• 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${\displaystyle A_n(t)}$ are really ofdegree$n-1$ for$n>0$.

A tabulation of the numbers in atriangular array is called theEuler triangle orEuler's triangle. It shares some common characteristics withPascal's triangle. Values of$A(n,k)$ (sequenceA008292 in theOEIS) for$0\le n\le 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

For larger values of$n$,$A(n,k)$ can also be calculated using therecursive formula^[3]

${\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}^{\prime }(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}(\genfrac{}{}{0ex}{}{n}{k})A_k(t)\cdot (t-1{)}^{n-1-k},\text{ for }n>1.}$

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 thefactorial${\displaystyle n!}$:$${\displaystyle \sum _{k=0}^{n}A(n,k)=n!.}$$(The summand${\displaystyle k=n}$ is 0 for${\displaystyle n>0}$, but is included to give the correct sum${\displaystyle A(0,0)=0!}$ when${\displaystyle n=0}$.)

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

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

Worpitzky's identity^[5] expresses$x^n$ as thelinear combination of Eulerian numbers withbinomial coefficients:

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

From this, it follows that

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

Eulerian numbers appear as the coefficients of thepolylogarithm for negative integer inputs:$${\displaystyle {\mathrm{Li}}_{-n}(z)=\frac{1}{(1-z{)}^{n+1}}\sum _{k=0}^{n-1}A(n,k)z^{n-k}(n=1,2,3,\dots ).}$$

Thealternating sum of the Eulerian numbers for a fixed value of$n$ is related to theBernoulli number$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)}{(\genfrac{}{}{0ex}{}{n-1}{k})}=0,\text{ for }n>1}$

and

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

The symmetry property implies:

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

The Eulerian numbers are involved in thegenerating function for the sequence ofn^th powers:

${\displaystyle \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^[6]

$${\displaystyle 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 theStirling number of the second kind.

The Eulerian numbers have two important geometric interpretations involvingconvex polytopes.

First of all, the identity

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

implies that the Eulerian numbers form the${\displaystyle h^{\ast }}$-vector of the standard${\displaystyle n}$-dimensionalhypercube, which is theconvex hull of all${\displaystyle 0,1}$-vectors in${\displaystyle {\mathbb{R}}^n}$.

Secondly, the identity$${\displaystyle A_n(t)=\sum _{k=0}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}k!(t-1{)}^{n-k}}$$means that the Eulerian numbers also form the${\displaystyle h}$-vector of thesimple polytope which isdual to the${\displaystyle n}$-dimensionalpermutohedron, which is the convex hull of all permutations of the vector${\displaystyle (1,2,\dots ,n)}$ in${\displaystyle {\mathbb{R}}^n}$.

Thehyperoctahedral group of order${\displaystyle n}$ is the group of allsigned permutations of the numbers${\displaystyle 1}$ to${\displaystyle n}$, meaning bijections${\displaystyle \pi }$ from the set${\displaystyle \{-n,-n+1,\dots ,-1,1,2,\dots ,n\}}$ to itself with the property that${\displaystyle \pi (-i)=-\pi (i)}$ for all${\displaystyle i}$. Just as thesymmetric group of order${\displaystyle n}$ (i.e., the group of all permutations of the numbers${\displaystyle 1}$ to${\displaystyle n}$) is theCoxeter group of Type${\displaystyle A_{n-1}}$, the hyperoctahedral group of order${\displaystyle n}$ is the Coxeter group of Type${\displaystyle B_n}$.

Given an element${\displaystyle \pi }$ of the hyperoctahedral group of order${\displaystyle n}$ aType B descent of${\displaystyle \pi }$ is an index${\displaystyle i\in \{0,1,\dots ,n-1\}}$ for which${\displaystyle \pi (i)>\pi (i-1)}$, with the convention that${\displaystyle \pi (0)=0}$. TheType B Eulerian number${\displaystyle B(n,k)}$ is the number of elements of the hyperoctahedral group of order${\displaystyle n}$ with exactly${\displaystyle k}$ descents; see Chow and Gessel.^[7]

The table of${\displaystyle B(n,k)}$ (sequenceA060187 in theOEIS) is

k n	0	1	2	3	4	5
0	1
1	1	1
2	1	6	1
3	1	23	23	1
4	1	76	230	76	1
5	1	237	1682	1682	237	1

The corresponding polynomials${\displaystyle M_n(x)=\sum _{k=0}^{n}B(n,k)x^k}$ are calledmidpoint Eulerian polynomials because of their use in interpolation and spline theory; see Schoenberg.^[8]

The Type B Eulerian numbers and polynomials satisfy many similar identities, and have many similar properties, as the Type A, i.e., usual, Eulerian numbers and polynomials. For example, for any${\displaystyle n\ge 1}$,

${\displaystyle \sum _{i=0}^{\mathrm{\infty }}(2i+1{)}^n{x}^i=\frac{M_n(x)}{(1-x{)}^{n+1}}.}$

And the Type B Eulerian numbers give the h-vector of the simple polytope dual to the Type B permutohedron.

In fact, one can define Eulerian numbers for anyfinite Coxeter group with analogous properties: see part III of the textbook of Petersen in the references.

The permutations of themultiset$\{1,1,2,2,\dots ,n,n\}$ which have the property that for eachk, all the numbers appearing between the two occurrences ofk in the permutation are greater thank are counted by thedouble factorial number$(2n-1)!!$. These are calledStirling permutations.

The Eulerian number of the second order, denoted$⟨⟨\genfrac{}{}{0ex}{}{n}{m}⟩⟩$, counts the number of all such Stirling permutations that have exactlym ascents. For instance, forn = 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 ⟨⟨\genfrac{}{}{0ex}{}{n}{k}⟩⟩=(2n-k-1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{k-1}⟩⟩+(k+1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{k}⟩⟩,}$

withinitial condition forn = 0, expressed inIverson bracket notation:

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

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

${\displaystyle 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 sequenceP_n(x):

${\displaystyle P_{n+1}(x)=(2nx+1)P_n(x)-x(x-1)P_n^{\mathrm{\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 anintegrating factor:

${\displaystyle (x-1{)}^{-2n-2}{P}_{n+1}(x)={\left(x(1-x{)}^{-2n-1}{P}_n(x)\right)}^{\mathrm{\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)}^{\mathrm{\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 Eulerian polynomials of the second order satisfy an identity analogous to the identity

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

satisfied by the usual Eulerian polynomials. Specifically, as proved by Gessel and Stanley,^[9] they satisfy the identity

${\displaystyle \sum _{m=0}^{\mathrm{\infty }}\left\{\genfrac{}{}{0ex}{}{n+m}{m}\right\}{x}^m=\frac{x{P}_n(x)}{(1-x{)}^{2n+1}}}$

where again the${\displaystyle \left\{\genfrac{}{}{0ex}{}{n}{k}\right\}}$ denote theStirling numbers of the second kind. (This appearance of the Stirling numbers explains the terminology "Stirling permutations.")

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 then-th row, which is also the value$P_n(1)$, is$(2n-1)!!$.

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

• (sequenceA008517 in theOEIS) following Riordan and Comtet,
• (sequenceA201637 in theOEIS) following Graham, Knuth, and Patashnik,
• (sequenceA340556 in theOEIS), extending the definition of Gessel and Stanley.

• 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.
• Carlitz, L. (1959). "Eulerian Numbers and polynomials".Math. Mag.32 (5):247–260.doi:10.2307/3029225.JSTOR 3029225.
• Gould, H. W. (1978)."Evaluation of sums of convolved powers using Stirling and Eulerian Numbers".Fib. Quart.16 (6):488–497.doi:10.1080/00150517.1978.12430271.
• Desarmenien, Jacques; Foata, Dominique (1992)."The signed Eulerian numbers".Discrete Math.99 (1–3):49–58.doi:10.1016/0012-365X(92)90364-L.
• Lesieur, Leonce; Nicolas, Jean-Louis (1992)."On the Eulerian Numbers M=max (A(n,k))".Europ. J. Combinat.13 (5):379–399.doi:10.1016/S0195-6698(05)80018-6.
• Butzer, P. L.; Hauss, M. (1993)."Eulerian numbers with fractional order parameters".Aequationes Mathematicae.46 (1–2):119–142.doi:10.1007/bf01834003.S2CID 121868847.
• Koutras, M.V. (1994)."Eulerian numbers associated with sequences of polynomials".Fib. Quart.32 (1):44–57.doi:10.1080/00150517.1994.12429255.
• Graham; Knuth; Patashnik (1994).Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley. pp. 267–272.
• Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (1999)."On certain summation problems and generalizations of Eulerian polynomials and numbers".Discrete Math.204 (1–3):237–247.doi:10.1016/S0012-365X(98)00379-3.
• Boyadzhiev, Khristo N. (2007). "Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials".arXiv:0710.1124 [math.CA].
• Petersen, T. Kyle (2015). "Eulerian numbers".Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. pp. 3–18.doi:10.1007/978-1-4939-3091-3_1.ISBN 978-1-4939-3090-6.

• Eulerian Polynomials atOEIS Wiki.
• "Eulerian Numbers".MathPages.com.
• Weisstein, Eric W."Eulerian Number".MathWorld.
• Weisstein, Eric W."Euler's Number Triangle".MathWorld.
• Weisstein, Eric W."Worpitzky's Identity".MathWorld.
• Weisstein, Eric W."Second-Order Eulerian Triangle".MathWorld.
• Euler-matrix (generalized rowindexes, divergent summation)

• Enumerative combinatorics
• Factorial and binomial topics
• Integer sequences
• Triangles of numbers

• Articles with short description
• Short description is different from Wikidata
• Use American English from March 2019
• All Wikipedia articles written in American English