This site is supported by donations to The OEIS Foundation.

Eulerian numbers, triangle of

From OeisWiki

Jump to: navigation, search


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 \ge 0, \,

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

A(d,k)|_{k=0}^{d} = \{1, (2^d-d-1), ..., (2^d-d-1), 1, 0^d\},\ d \ge 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.

Contents

Euler's triangle

The rectangular version of Eulerian numbers triangle[1]
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 \ge 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 \,\ge\, 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 \ge 1,\ 0 \le k \le 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 \,\ge\, 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 \,\ge\, 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 \,\ge\, 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 \ge 0, \,

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

This means that the \scriptstyle n\,th, \scriptstyle n \,\ge\, 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 \ge 0, \,

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

Eulerian numbers triangle rows alternating sign sums

Eulerian numbers (rectangular) triangle columns

Table of columns sequences

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

Eulerian numbers triangle columns sequences
k \, A(k+i, k),\ i \ge 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 \,\ge\, 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 \,\ge\, 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 0th (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 \ge 0, \,

with generating function

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

The triangle rows being symmetric (if we exclude the zero valued entries \scriptstyle A(n,n),\ n \,\ge\, 1 \,), the \scriptstyle (k+1) \,th (from the right) falling diagonal is identical to the \scriptstyle k \,th column, with \scriptstyle k \,\ge\, 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 (rectangular) triangle rising diagonals

Eulerian numbers (rectangular) triangle rising diagonals sums

Eulerian numbers (rectangular) triangle rising diagonals alternating sign sums

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 \,\ge\, 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 \,\ge\, 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 \,\ge\, 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 \,\le\, k \,\le\, n \,.

Notes

  1. Weisstein, Eric W., Euler's Number Triangle, From MathWorld--A Wolfram Web Resource.

External links

Personal tools