Eulerian numbers, triangle of

This article needs more work.

Please help by expanding it!

The triangle of Eulerian numbers is also called Euler's triangle. The Eulerian numbers are the coefficients in the Eulerian polynomials. The Eulerian numbers are also the number of permutations of {1, 2, .., $\scriptstyle n\,$} with $\scriptstyle k\,$ ascents. The Eulerian polynomials appear, among others, in the expression of the generating function of powers (generating function of regular orthotopic numbers)

$G_{\{n^{d}\}}(x)={\frac {x\ A_{d}(x)}{(1-x)^{d+1}}},\,$

where

$A_{d}(x)=\sum _{k=0}^{d}A(d,k)\ x^{k},\ d\geq 0,\,$

is the $\scriptstyle d\,$^th Eulerian polynomial (with degree $\scriptstyle d-1\,$ for $\scriptstyle d\,\geq \,1\,$) [1] whose Eulerian numbers

$A(d,k)|_{k=0}^{d}=\{1,(2^{d}-d-1),...,(2^{d}-d-1),1,0^{d}\},\ d\geq 0,\,$

can be recursively generated with the triangle of Eulerian numbers.

In the following, $\scriptstyle n\,$ will be used for the degree of the Eulerian polynomials and their associated Eulerian numbers (instead of $\scriptstyle d\,$ for dimension of the orthotopic numbers used above) so as to follow the conventional notation for number triangles.

Euler's triangle

The rectangular version of Eulerian numbers triangle

n = 0	1
1	1	0
2	1	1	0
3	1	4	1	0
4	1	11	11	1	0
5	1	26	66	26	1	0
6	1	57	302	302	57	1	0
7	1	120	1191	2416	1191	120	1	0
8	1	247	4293	15619	15619	4293	247	1	0
9	1	502	14608	88234	156190	88234	14608	502	1	0
10	1	1013	47840	455192	1310354	1310354	455192	47840	1013	1	0
11	1	2036	152637	2203488	9738114	15724248	9738114	2203488	152637	2036	1	0
12	1	4083	478271	10187685	66318474	162512286	162512286	66318474	10187685	478271	4083	1	0
	k = 0	1	2	3	4	5	6	7	8	9	10	11	12

Recursion rule

$A(0,0)=1,\,$

$A(n,k)=(n-k)\ A(n-1,k-1)+(k+1)\ A(n-1,k),\ n\geq 1,\,$

where the empty cells outside the triangle are considered zero valued.

Formulae

The Eulerian numbers are equal to the number of permutations of {1, 2, .., $\scriptstyle n\,$} with $\scriptstyle k\,$ ascents

$A(n,k)=\left\langle {n \atop k}\right\rangle =\sum _{j=0}^{k}(-1)^{j}{\binom {n+1}{j}}(k-j+1)^{n}.\,$

Eulerian numbers triangle rows

The Eulerian numbers triangle rows entries give the infinite sequence of finite sequences

{{1}, {1, 0}, {1, 1, 0}, {1, 4, 1, 0}, {1, 11, 11, 1, 0}, {1, 26, 66, 26, 1, 0}, {1, 57, 302, 302, 57, 1, 0}, {1, 120, 1191, 2416, 1191, 120, 1, 0}, {1, 247, 4293, 15619, 15619, 4293, 247, 1, 0}, {1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1, 0}, {1, 1013, 47840, 455192, 1310354, 1310354, 455192, 47840, 1013, 1, 0}, ...}

The concatenation of the infinite sequence of finite sequences of the Eulerian numbers triangle rows entries gives the infinite sequence (A173018)

{1, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 11, 11, 1, 0, 1, 26, 66, 26, 1, 0, 1, 57, 302, 302, 57, 1, 0, 1, 120, 1191, 2416, 1191, 120, 1, 0, 1, 247, 4293, 15619, 15619, 4293, 247, 1, 0, 1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1, 0, 1, 1013, 47840, 455192, 1310354, 1310354, 455192, 47840, 1013, 1, 0, ...}

The rows without the last zero valued entries (entries from $\scriptstyle k\,=\,0\,$ to $\scriptstyle n-1\,$ for $\scriptstyle n\,\geq \,1\,$) are symmetric with respect to their centers $\scriptstyle {\big (}{\frac {n-1}{2}}{\big )}\,$, i.e.

$A(n,k)=A(n,(n-1)-k),\ n\geq 1,\ 0\leq k\leq n-1.\,$

The Eulerian numbers triangle rows nonzero entries ($\scriptstyle k\,=\,0\,$ entry for $\scriptstyle n\,=\,0\,$, entries from $\scriptstyle k\,=\,0\,$ to $\scriptstyle n-1\,$ for $\scriptstyle n\,\geq \,1\,$) give the infinite sequence of finite sequences

{{1}, {1}, {1, 1}, {1, 4, 1}, {1, 11, 11, 1}, {1, 26, 66, 26, 1}, {1, 57, 302, 302, 57, 1}, {1, 120, 1191, 2416, 1191, 120, 1}, {1, 247, 4293, 15619, 15619, 4293, 247, 1}, {1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1}, {1, 1013, 47840, 455192, 1310354, 1310354, 455192, 47840, 1013, 1}, ...}

The concatenation of the infinite sequence of finite sequences of the Eulerian numbers triangle rows nonzero entries gives the infinite sequence: (A008292$\scriptstyle (i)\,$, $\scriptstyle i\,\geq \,1\,$, with 1 for $\scriptstyle i\,=\,0\,$ prepended)

{1, 1, 1, 1, 1, 4, 1, 1, 11, 11, 1, 1, 26, 66, 26, 1, 1, 57, 302, 302, 57, 1, 1, 120, 1191, 2416, 1191, 120, 1, 1, 247, 4293, 15619, 15619, 4293, 247, 1, 1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1, 1, 1013, 47840, 455192, 1310354, 1310354, 455192, 47840, 1013, 1, ...}

Eulerian numbers triangle rows sums

The sums of the respective finite sequences give the infinite sequence (A000142$\scriptstyle (i)\,$, $\scriptstyle i\,\geq \,0\,$)

{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, ...}

with members given by the formula

$\sum _{k=0}^{n}A(n,k)=n!,\ n\geq 0,\,$

where $\scriptstyle A(n,n)\,=\,0,\ n\,\geq \,1.\,$

This means that the $\scriptstyle n\,$^th, $\scriptstyle n\,\geq \,0\,$, Eulerian polynomial, evaluated at $\scriptstyle x\,=\,1\,$, gives $\scriptstyle n\,$!:

$A_{n}(x)|_{x=1}={{\bigg \{}\sum _{k=0}^{n}A(n,k)\ x^{k}{\bigg \}}}{\bigg |}_{x=1}=n!,\ n\geq 0,\,$

where $\scriptstyle A(n,n)\,=\,0,\ n\,\geq \,1.\,$

Eulerian numbers (rectangular) triangle columns

Table of columns sequences

The $\scriptstyle i\,$^th, $\scriptstyle i\,\geq \,0\,$, member of column $\scriptstyle k\,$ appears in row $\scriptstyle k+i\,$.

Eulerian numbers triangle columns sequences

$k\,$	$A(k+i,k),\ i\geq 0\,$ sequences	A-number
0	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...}	A000012
1	{0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, 2036, 4083, 8178, 16369, 32752, 65519, 131054, 262125, 524268, 1048555, 2097130, 4194281, 8388584, 16777191, ...}	A000295
2	{0, 1, 11, 66, 302, 1191, 4293, 14608, 47840, 152637, 478271, 1479726, 4537314, 13824739, 41932745, 126781020, 382439924, 1151775897, 3464764515, ...}	A000460
3	{0, 1, 26, 302, 2416, 15619, 88234, 455192, 2203488, 10187685, 45533450, 198410786, 848090912, 3572085255, 14875399450, 61403313100, 251732291184, ...}	A000498
4	{0, 1, 57, 1191, 15619, 156190, 1310354, 9738114, 66318474, 423281535, 2571742175, 15041229521, 85383238549, 473353301060, 2575022097600, 13796160184500, ...}	A000505
5	{0, 1, 120, 4293, 88234, 1310354, 15724248, 162512286, 1505621508, 12843262863, 102776998928, 782115518299, 5717291972382, 40457344748072, 278794377854832, ...}	A000514
6	{0, 1, 247, 14608, 455192, 9738114, 162512286, 2275172004, 27971176092, 311387598411, 3207483178157, 31055652948388, 285997074307300, 2527925001876036, ...}	A001243
7	{0, 1, 502, 47840, 2203488, 66318474, 1505621508, 27971176092, 447538817472, 6382798925475, 83137223185370, 1006709967915228, 11485644635009424, ...}	A001244
8	{0, 1, 1013, 152637, 10187685, ...}	A??????
9	{0, 1, 2036, 478271, ...}	A??????
10	{0, 1, 4083, ...}	A??????
11	{0, 1, ...}	A??????

Table of columns sequences related formulae

The $\scriptstyle i\,$^th, $\scriptstyle i\,\geq \,0\,$, member of column $\scriptstyle k\,$ appears in row $\scriptstyle k+i\,$.

Eulerian numbers triangle columns sequences related formulae

$k\,$	Formulae $A(k+i,k)=\,$ $\,$	Generating function for $\scriptstyle i\,$ th ($\scriptstyle i\,\geq \,0\,$) member of column $G_{A}(k,x)=\,$ $\,$	Order of basis $g_{A}(k)=\,$	Differences $A(k+i,k)-\,$ $A(k+i-1,k)=\,$	Partial sums $\sum _{i=1}^{m}A(k+i,k)=\,$	Partial sums of reciprocals $\sum _{i=1}^{m}{1 \over {A(k+i,k)}}=\,$	Sum of Reciprocals $\sum _{i=1}^{\infty }{1 \over {A(k+i,k)}}=\,$
0	$1\,$	${\frac {1}{1-x}}\,$	$\,$	$\,$	$\,$	$\,$	$\,$
1	$2^{i+2}-(i+2)-1\,$	${\frac {x}{(1-x)^{2}(1-2x)}}\,$	$\,$	$\,$	$\,$	$\,$	$\,$
2	$\,$	${\frac {x(1+x-4x^{2})}{(1-x)^{3}(1-2x)^{2}(1-3x)}}\,$	$\,$	$\,$	$\,$	$\,$	$\,$
3	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
4	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
5	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
6	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
7	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
8	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
9	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
10	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$
11	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$	$\,$

Eulerian numbers (rectangular) triangle falling diagonals

The 0^th (from the right) falling diagonal gives the sequence (A000007)

{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...}

which is given by the formula

$A(n,n)=0^{n},\ n\geq 0,\,$

with generating function

$G_{\{A(n,n)\}}(x)=1,\ n\geq 0.\,$

The triangle rows being symmetric (if we exclude the zero valued entries $\scriptstyle A(n,n),\ n\,\geq \,1\,$), the $\scriptstyle (k+1)\,$^th (from the right) falling diagonal is identical to the $\scriptstyle k\,$^th column, with $\scriptstyle k\,\geq \,0\,$.

Table of falling diagonals sequences

See table of columns sequences.

Table of falling diagonals sequences related formulae

See table of columns sequences related formulae.

Eulerian numbers triangle middle and central elements

The Eulerian numbers triangle middle elements or maximal Eulerian numbers (of $\scriptstyle k\,=\,0\,$ to $\scriptstyle n-1,\ n\,\geq \,1\,$), are the number of permutations of {1, 2, .., $\scriptstyle n\,$} with $\scriptstyle {\big \lfloor }{\frac {n}{2}}{\big \rfloor }\,$ ascents (A006551)

{1, 1, 4, 11, 66, 302, 2416, 15619, 156190, 1310354, 15724248, 162512286, 2275172004, 27971176092, 447538817472, 6382798925475, 114890380658550, 1865385657780650, 37307713155613000, ...}

given by the formula

$T(n,{\bigg \lfloor }{\frac {n}{2}}{\bigg \rfloor })=A(n,{\bigg \lfloor }{\frac {n}{2}}{\bigg \rfloor })=\sum _{j=0}^{{\big \lfloor }{\frac {n}{2}}{\big \rfloor }}(-1)^{j}{\binom {n+1}{j}}{\bigg (}{\bigg \lfloor }{\frac {n}{2}}{\bigg \rfloor }-j+1{\bigg )}^{n},\,$

where

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

The Eulerian numbers triangle central elements (of $\scriptstyle k\,=\,0\,$ to $\scriptstyle n,\ n\,=\,2m,\ m\,\geq \,0\,$), are the number of permutations $\scriptstyle A(2m,m)\,$ of {1, 2, .., $\scriptstyle 2m\,$} with $\scriptstyle m\,$ ascents (A180056)

{1, 1, 11, 302, 15619, 1310354, 162512286, 27971176092, 6382798925475, 1865385657780650, 679562217794156938, 301958232385734088196, 160755658074834738495566, ...}

given by the formula

$T(2m,m)=A(2m,m)=\sum _{j=0}^{m}(-1)^{j}{\binom {2m+1}{j}}(m-j+1)^{2m},\,$

where

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

The Eulerian numbers triangle central elements (of $\scriptstyle k\,=\,0\,$ to $\scriptstyle n,\ n\,=\,2m-1,\ m\,\geq \,0\,$), are the number of permutations $\scriptstyle A(2m-1,m)\,$ of {1, 2, .., $\scriptstyle 2m-1\,$} with $\scriptstyle m\,$ ascents (A025585)

{1, 4, 66, 2416, 156190, 15724248, 2275172004, 447538817472, 114890380658550, 37307713155613000, 14950368791471452636, 7246997577257618116704, 4179647109945703200884716, ...}

given by the formula

$T(2m-1,m)=A(2m-1,m)=\sum _{j=0}^{m}(-1)^{j}{\binom {2m}{j}}(m-j+1)^{2m-1},\,$

where

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

See also

• A007338 Multiplicative encoding of the Eulerian number triangle.
• A008517 Second-order Eulerian triangle $\scriptstyle T(n,k),\ 1\,\leq \,k\,\leq \,n\,$.

External links

• Eulerian Numbers at MathPages.
• Weisstein, Eric W., Eulerian Number, from MathWorld—A Wolfram Web Resource.
• Weisstein, Eric W., Euler's Number Triangle, from MathWorld—A Wolfram Web Resource.
• Eulerian number—Wikipedia.org.