Eulerian number#Basic properties

The Eulerian polynomials $A\_n(t)$ are defined by the exponential generating function

:$\backslash sum\_\{n=0\}^\{\backslash infty\}\; A\_\{n\}(t)\; \backslash ,\backslash frac\{x^n\}\{n!\}\; =\; \backslash frac\{t-1\}\{t\; -\; e^\{(t-1)\backslash ,x\}\}\; =\; \backslash left(1-\backslash frac\{e^\{(t-1)x\}-1\}\{t-1\}\backslash right)^\{-1\}.$

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

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

An explicit formula for $A(n,k)$ is(L. Comtet 1974, p. 243)

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

:

For larger values of $n$, $A(n,k)$ can also be calculated using the recursive formula{{cite book |last1=Comtet |first1=Louis |title=Advanced Combinatorics |page=51 |url=https://ia801306.us.archive.org/27/items/Comtet_Louis_-_Advanced_Coatorics/Comtet_Louis_-_Advanced_Combinatorics.pdf}}

:$A(n,k)=(n-k)\backslash ,A(n-1,k-1)\; +\; (k+1)\backslash ,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

:

Applying the recurrence to one example, we may find

:$A(4,1)=(4-1)\backslash ,A(3,0)\; +\; (1+1)\backslash ,A(3,1)=3\; \backslash cdot\; 1\; +\; 2\; \backslash cdot\; 4\; =\; 11.$

Likewise, the Eulerian polynomials can be computed by the recurrence

:$A\_\{0\}(t)\; =\; 1,$

:$A\_\{n\}(t)\; =\; A\_\{n-1\}\text{'}(t)\backslash cdot\; t\backslash ,(1-t)\; +\; A\_\{n-1\}(t)\backslash cdot\; (1+(n-1)\backslash ,t),\backslash text\{\; for\; \}\; n\; >\; 1.$

The second formula can be cast into an inductive form,

:$A\_\{n\}(t)\; =\; \backslash sum\_\{k=0\}^\{n-1\}\; \backslash binom\{n\}\{k\}\; A\_\{k\}(t)\backslash cdot\; (t-1)^\{n-1-k\},\; \backslash 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 $n$ elements, so their sum equals the factorial $n!$. I.e.

:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; =\; n!,\; \backslash 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\backslash colon\; \backslash mathbb\{R\}\; \backslash rightarrow\; \backslash mathbb\{C\}$ integrable on the interval $(0,\; n)$Exercise 6.65 in Concrete Mathematics by Graham, Knuth and Patashnik.

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

Worpitzky's identity{{cite journal |last1=Worpitzky |first1=J. |title=Studien über die Bernoullischen und Eulerschen Zahlen |journal=Journal für die reine und angewandte Mathematik |date=1883 |volume=94 |pages=203–232 |url=https://eudml.org/doc/148532}} expresses $x^n$ as the linear combination of Eulerian numbers with binomial coefficients:

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

From it, it follows that

:$\backslash sum\_\{k=1\}^\{m\}k^n=\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; \backslash binom\{m+k+1\}\{n+1\}.$

The alternating sum of the Eulerian numbers for a fixed value of $n$ is related to the Bernoulli number $B\_\{n+1\}$

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

Furthermore,

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

and

:$\backslash sum\_\{k=0\}^\{n-1\}(-1)^k\; \backslash frac\{A(n,k)\}\{\backslash binom\{n\}\{k\}\}=(n+1)B\_\{n\},\; \backslash text\{\; for\; \}\; n\; >\; 1$

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:

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

An explicit expression for Eulerian polynomials is{{Cite journal |last1=Qi |first1=Feng |last2=Guo |first2=Bai-Ni |date=2017-08-01 |title=Explicit formulas and recurrence relations for higher order Eulerian polynomials |journal=Indagationes Mathematicae |volume=28 |issue=4 |pages=884–891 |doi=10.1016/j.indag.2017.06.010 |issn=0019-3577|doi-access=free }}

$$A\_n(t)\; =\; \backslash sum\_\{k=0\}^n\; \backslash left\backslash \{\; \{n\; \backslash atop\; k\}\; \backslash right\backslash \}\; k!\; (t-1)^\{n-k\}$$

where $\backslash left\backslash \{\; \{n\; \backslash atop\; k\}\; \backslash right\backslash \}$ is the Stirling number of the second kind.

The permutations of the multiset $\backslash \{1,\; 1,\; 2,\; 2,\; \backslash ldots,\; n,\; n\backslash \}$ 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 $\backslash left\backslash langle\; \backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; m\}\; \backslash right\backslash rangle\; \backslash !\; \backslash right\backslash 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:

:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; (2n-k-1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k-1\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; +\; (k+1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle,$

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

:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{0\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; [k=0].$

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

:$P\_n(x)\; :=\; \backslash sum\_\{k=0\}^n\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash 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^\backslash 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)\; =\; \backslash left(\; x\backslash ,(1-x)^\{-2n-1\}\; P\_n(x)\; \backslash right)^\backslash prime$

so that the rational function

:$u\_n(x)\; :=\; (x-1)^\{-2n\}\; P\_\{n\}(x)$

satisfies a simple autonomous recurrence:

:$u\_\{n+1\}\; =\; \backslash left(\; \backslash frac\{x\}\{1-x\}\; u\_n\; \backslash right)^\backslash prime,\; \backslash quad\; 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:

:

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:

• {{OEIS|A008517}} following Riordan and Comtet,
• {{OEIS|A201637}} following Graham, Knuth, and Patashnik,
• {{OEIS|A340556}}, 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.
• {{cite journal|first1=L. |last1=Carlitz|title=Eulerian Numbers and polynomials | year=1959|journal=Math. Mag.|volume=32 | number=5 | pages=247–260|doi=10.2307/3029225|jstor=3029225}}
• {{cite journal|first1=H. W. |last1=Gould|title=Evaluation of sums of convolved powers using Stirling and Eulerian Numbers|year=1978|journal=Fib. Quart.|volume =16 |pages=488–497|number=6|doi=10.1080/00150517.1978.12430271 |url=https://www.fq.math.ca/16-6.html}}
• {{cite journal|first1=Jacques | last1=Desarmenien | first2=Dominique | last2=Foata | title=The signed Eulerian numbers| journal=Discrete Math.

|year=1992|volume=99 | number=1–3| pages=49–58|doi=10.1016/0012-365X(92)90364-L| doi-access=free}}

• {{cite journal|year=1992|journal=Europ. J. Combinat. | volume=13 | pages=379–399|number=5|title= On the Eulerian Numbers M=max (A(n,k))|first1=Leonce |last1=Lesieur | first2=Jean-Louis | last2=Nicolas|doi=10.1016/S0195-6698(05)80018-6|doi-access=free}}
• {{cite journal

|first1=P. L. |last1=Butzer | first2=M. |last2=Hauss

|title=Eulerian numbers with fractional order parameters

|journal=Aequationes Mathematicae | year=1993 | volume=46|issue=1–2 |pages=119–142

|url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002610515 | doi=10.1007/bf01834003

|s2cid=121868847 }}

• {{cite journal|first1=M.V. |last1=Koutras|title=Eulerian numbers associated with sequences of polynomials|journal=Fib. Quart.|year=1994|pages=44–57|volume=32|number=1|doi=10.1080/00150517.1994.12429255 |url=https://www.fq.math.ca/32-1.html}}
• {{cite book|last1=Graham|

last2=Knuth|last3=Patashnik|year=1994|title=Concrete Mathematics: A Foundation for Computer Science|edition=2nd|publisher=Addison-Wesley|pages=267–272}}

• {{cite journal|first1=Leetsch C. |last1=Hsu |author1-link=Leetsch C. Hsu | first2=Peter | last2=Jau-Shyong Shiue| title=On certain summation problems and generalizations of Eulerian polynomials and numbers|journal=Discrete Math. | volume=204 | year=1999 |issue=1–3 | doi=10.1016/S0012-365X(98)00379-3|pages=237–247|doi-access=free }}
• {{cite arXiv|eprint=0710.1124 |title=Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials|year=2007|first1=Khristo N. |last1=Boyadzhiev|class=math.CA}}
• {{cite book |first1=T. Kyle|last1= Petersen|year=2015|title = Eulerian Numbers |chapter = Eulerian numbers |series= Birkhäuser Advanced Texts Basler Lehrbücher|publisher=Birkhäuser|doi=10.1007/978-1-4939-3091-3_1|pages=3–18|isbn= 978-1-4939-3090-6}}

{{Reflist|colwidth=30em}}

• [http://oeis.org/wiki/Eulerian_polynomials Eulerian Polynomials] at OEIS Wiki.
• {{MathPages|id=home/kmath012/kmath012|title=Eulerian Numbers}}
• {{MathWorld|title=Eulerian Number|urlname=EulerianNumber}}
• {{MathWorld|title=Euler's Number Triangle|urlname=EulersNumberTriangle}}
• {{MathWorld|title=Worpitzky's Identity|urlname=WorpitzkysIdentity}}
• {{MathWorld|title=Second-Order Eulerian Triangle|urlname=Second-OrderEulerianTriangle}}
• [http://go.helms-net.de/math/binomial_new/01_12_Eulermatrix.pdf Euler-matrix] (generalized rowindexes, divergent summation)

Category:Enumerative combinatorics

Category:Factorial and binomial topics

Category:Integer sequences

Category:Triangles of numbers