View source for Eulerian number

{{distinguish|Euler number|Euler's number}}
{{Use American English|date = March 2019}}
{{Short description|Polynomial sequence}}
In [[combinatorics]], the '''Eulerian number''' ''A''(''n'', ''m''), is the number of [[permutation]]s of the numbers 1 to ''n'' in which exactly ''m'' elements are greater than the previous element (permutations with ''m'' "ascents"). They are the coefficients of the '''Eulerian polynomials''':
:<math>A_{n}(t) = \sum_{m=0}^{n} A(n,m)\ t^{m}.</math>

The Eulerian polynomials are defined by the exponential generating function

: <math>
\sum_{n=0}^{\infty} A_{n}(t) \cdot \frac{x^n}{n!} = \frac{t-1}{t - \mathrm{e}^{(t-1) x}}. </math>

The Eulerian polynomials can be computed by the recurrence

:<math>A_{0}(t) = 1,</math>

: <math>
A_{n}(t) = t (1-t)\cdot A_{n-1}'(t) + A_{n-1}(t)\cdot (1+(n-1)t),\quad n \ge 1.
</math>

An equivalent way to write this definition is to set the Eulerian polynomials inductively by

:<math>A_{0}(t) = 1,</math>

: <math>
A_{n}(t) = \sum_{k=0}^{n-1} \binom{n}{k} A_{k}(t)\cdot (t-1)^{n-1-k},\quad n \ge 1.
</math>

Other notations for ''A''(''n'', ''m'') are ''E''(''n'', ''m'') and <math> \scriptstyle \left\langle {n \atop m} \right\rangle </math>.

==History==
[[Image:EulerianPolynomialsByEuler1755.png|right|303px|thumb|Shows 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 number.]]
In 1755 [[Leonhard Euler]] investigated in his book ''Institutiones calculi differentialis'' polynomials {{math|1=''α''<sub>1</sub>(''x'')&nbsp;=&nbsp;1}}, {{math|1=''α''<sub>2</sub>(''x'')&nbsp;=&nbsp;''x''&nbsp;+&nbsp;1}}, {{math|1=''α''<sub>3</sub>(''x'')&nbsp;=&nbsp;''x''<sup>2</sup>&nbsp;+&nbsp;4''x''&nbsp;+&nbsp;1}}, etc. (see the facsimile). These polynomials are a shifted form of what are now called the Eulerian polynomials ''A''<sub>''n''</sub>(''x'').

==Basic properties==<!--linked to by [[Euler triangle]] & [[Euler's triangle]]-->
For a given value of ''n''&nbsp;&gt;&nbsp;0, the index ''m'' in ''A''(''n'', ''m'') can take values from 0 to ''n''&nbsp;&minus;&nbsp;1. For fixed ''n'' there is a single permutation which has 0 ascents: (''n'', ''n''&nbsp;&minus;&nbsp;1, ''n''&nbsp;&minus;&nbsp;2, ..., 1). There is also a single permutation which has ''n''&nbsp;&minus;&nbsp;1 ascents; this is the rising permutation (1, 2, 3, ..., ''n''). Therefore ''A''(''n'', 0) and ''A''(''n'', ''n''&nbsp;&minus;&nbsp;1) are 1 for all values of ''n''.

Reversing a permutation with ''m'' ascents creates another permutation in which there are ''n''&nbsp;&minus;&nbsp;''m''&nbsp;&minus;&nbsp;1 ascents.
Therefore ''A''(''n'', ''m'') = ''A''(''n'', ''n''&nbsp;&minus;&nbsp;''m''&nbsp;&minus;&nbsp;1).

Values of ''A''(''n'', ''m'') can be calculated "by hand" for small values of ''n'' and ''m''. For example

:{| class="wikitable"
|-
! ''n''
! ''m''
! Permutations
! ''A''(''n'', ''m'')
|-
| 1
| 0
| (1)
| ''A''(1,0) = 1
|-
|rowspan="2" | 2
| 0
| (2, 1)
| ''A''(2,0) = 1
|-
| 1
| (1, '''2''')
| ''A''(2,1) = 1
|-
|rowspan="3" | 3
| 0
| (3, 2, 1)
| ''A''(3,0) = 1
|-
| 1
| (1, '''3''', 2) (2, 1, '''3''') (2, '''3''', 1) (3, 1, '''2''')
| ''A''(3,1) = 4
|-
| 2
| (1, '''2''', '''3''')
| ''A''(3,2) = 1
|}

For larger values of ''n'', ''A''(''n'', ''m'') can be calculated using the [[recursion|recursive]] formula

:<math>A(n,m)=(n-m)A(n-1,m-1) + (m+1)A(n-1,m).</math>

For example

:<math>A(4,1)=(4-1)A(3,0) + (1+1)A(3,1)=3 \times 1 + 2 \times 4 = 11.</math>

Values of ''A''(''n'', ''m'') {{OEIS|id=A008292}} for 0 ≤ ''n'' ≤ 9 are:

:{| class="wikitable" {{ts|ar}}
|-
! {{diagonal split header|''n''&nbsp;|&nbsp;''m''}}
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 8
|-
! 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
|}

The above [[triangular array]] is called the '''Euler triangle''' or '''Euler's triangle''', and it shares some common characteristics with [[Pascal's triangle]]. The sum of row ''n'' is the [[factorial]] ''n''<nowiki>!</nowiki>.

==Explicit formula==
An explicit formula for ''A''(''n'', ''m'') is

:<math>A(n,m)=\sum_{k=0}^{m}(-1)^k \binom{n+1}{k} (m+1-k)^n.</math>

One can see from this formula, as well as from the combinatorial interpretation, that <math>A(n,n) = 0</math> for <math>n>0</math>, so that <math>A_{n}(t)</math> is a [[polynomial]] of [[Degree_of_a_polynomial|degree]] <math>n-1</math> for <math>n>0</math>.

==Summation properties==
It is clear from the combinatorial definition that the sum of the Eulerian numbers for a fixed value of ''n'' is the total number of permutations of the numbers 1 to ''n'', so

:<math>\sum_{m=0}^{n-1}A(n,m)=n! \text{ for }n \ge 1.</math>

The [[alternating sum]] of the Eulerian numbers for a fixed value of ''n'' is related to the [[Bernoulli number]] ''B''<sub>''n''+1</sub>

:<math>\sum_{m=0}^{n-1}(-1)^{m}A(n,m)=\frac{2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1} \text{ for }n \ge 1.</math>

Other summation properties of the Eulerian numbers are:

:<math>\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n-1}{m}}=0 \text{ for }n \ge 2,</math>

:<math>\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n}{m}}=(n+1)B_{n} \text{ for }n \ge 2,</math>

where ''B''<sub>''n''</sub> is the ''n''<sup>th</sup> Bernoulli number.

==Identities==
The Eulerian numbers are involved in the [[generating function]] for the sequence of ''n''<sup>th</sup> powers:
:<math>\sum_{k=0}^{\infty}k^n x^k = \frac{\sum_{m=0}^{n-1}A(n,m)x^{m+1}}{(1-x)^{n+1}} = \frac{x \cdot A_n(x)}{(1-x)^{n+1}}</math>
for <math>n \geq 0</math>.  This assumes that 0<sup>0</sup> = 0 and ''A''(0,0) = 1 (since there is one permutation of no elements, and it has no ascents).

'''Worpitzky's identity'''<ref>{{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}}</ref> expresses ''x''<sup>''n''</sup> as the [[linear combination]] of Eulerian numbers with [[binomial coefficient]]s:
:<math>x^n=\sum_{m=0}^{n-1}A(n,m)\binom{x+m}{n}.</math>

It follows from Worpitzky's identity that 
:<math>\sum_{k=1}^{N}k^n=\sum_{m=0}^{n-1}A(n,m)\binom{N+1+m}{n+1}.</math>

Another interesting identity is
:<math>\frac{e}{1-ex}=\sum_{n=0}^\infty\frac{A_n(x)}{n!(1-x)^{n+1}}.</math>
The numerator on the right-hand side is the  Eulerian polynomial.

For a fixed function <math>f: \mathbb{R} \rightarrow \mathbb{C}</math> which is integrable on <math>(0, n)</math> we have the integral formula <ref>Exercise 6.65 in ''Concrete Mathematics'' by Graham, Knuth and Patashnik.</ref>

:<math>\int_0^1 \cdots \int_0^1 f\left(\left\lfloor x_1 + \cdots + x_n\right\rfloor\right) dx_1 \cdots dx_n = \sum_k A(n, k) \frac{f(k)}{n!}. </math>

==Eulerian numbers of the second kind==
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 (2''n''−1)!!. 
The Eulerian number of the second kind, denoted <math> \scriptstyle \left\langle \! \left\langle {n \atop m} \right\rangle \! \right\rangle </math>, 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 kind satisfy the recurrence relation, that follows directly from the above definition:

:<math> \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle = (2n-m-1) \left\langle \!\! \left\langle {n-1 \atop m-1} \right\rangle \!\! \right\rangle + (m+1) \left\langle \!\! \left\langle {n-1 \atop m} \right\rangle \!\! \right\rangle, </math>

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

:<math> \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle = [m=0]. </math>

Correspondingly, the Eulerian polynomial of second kind, here denoted ''P''<sub>''n''</sub> (no standard notation exists for them) are

:<math>P_n(x) := \sum_{m=0}^n  \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle x^m </math>

and the above recurrence relations are translated into a recurrence relation for the sequence ''P''<sub>''n''</sub>(''x''):

:<math> P_{n+1}(x) = (2nx+1) P_n(x) - x(x-1) P_n^\prime(x) </math>

with initial condition

:<math> P_0(x) = 1. </math>

The latter recurrence may be written in a somehow more compact form by means of an integrating factor:

:<math> (x-1)^{-2n-2} P_{n+1}(x) = \left( x(1-x)^{-2n-1} P_n(x) \right)^\prime </math>

so that the rational function

:<math> u_n(x) := (x-1)^{-2n} P_{n}(x) </math>

satisfies a simple autonomous recurrence:

:<math> u_{n+1} = \left( \frac{x}{1-x} u_n \right)^\prime, \quad u_0=1, </math>

whence one obtains the Eulerian polynomials as ''P''<sub>''n''</sub>(''x'') = (1−''x'')<sup>2''n''</sup> ''u''<sub>''n''</sub>(''x''), and the Eulerian numbers of the second kind as their coefficients.

Here are some values of the second order Eulerian numbers {{OEIS|A008517}}:

:{| class="wikitable" {{ts|ar}}
|-
! {{diagonal split header|''n''&nbsp;|&nbsp;''m''}}
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 8
|-
! 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''<sub>''n''</sub>(1), is (2''n'' − 1)!!.

==References==
* 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}}
* {{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|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}}
* {{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))|first=Leonce |last1=Lesieur | first2=Jean-Louis | last2=Nicolas|doi=10.1016/S0195-6698(05)80018-6}}
* {{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|pages=119–142
|url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002610515 | doi=10.1007/bf01834003
}}
* {{cite journal|first1=M.V. |last1=Koutras|title=Eulerian numbers associated with sequences of polynomials|journal=Fib. Quart.|year=1994|pages=44|volume=32|number=1|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}}
<!--See also http://www.combinatorics.org/Volume_4/PDF/v4i2r18.pdf -->
*{{cite article|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 | doi=10.1016/S0012-365X(98)00379-3|pages=237-247}}
* {{cite arxiv|eprint=0710.1124 |title=Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials|year=2007|first1=Khristo N. |last1=Boyadzhiev}}
* {{cite book|first1=T. Kyle|last1= Petersen|year=2015|title=Eulerian Numbers|publisher=Birkhäuser|doi=10.1007/978-1-4939-3091-3_1|pages=3–18}}

==References==
<references />

==External links==
*[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]]