Euler's Triangle

In combinatorics, the Eulerian number ''A''(''n'', ''m'') is the number of permutations 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:
:$A_(t) = \sum_^ A(n,m)\ t^.$

The Eulerian polynomials are defined by the exponential generating function

: $\sum_^ A_(t) \cdot \frac = \frac.$

The Eulerian polynomials can be computed by the recurrence

:$A_(t) = 1,$

: $A_(t) = t (1-t)\cdot A_'(t) + A_(t)\cdot (1+(n-1)t),\quad n \ge 1.$

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

:$A_(t) = 1,$

: $A_(t) = \sum_^ \binom A_(t)\cdot (t-1)^,\quad n \ge 1.$

Other notations for ''A''(''n'', ''m'') are ''E''(''n'', ''m'') and $\textstyle \left\langle \right\rangle$.

History

In 1755, in his book ''Institutiones calculi differentialis'', Leonhard Euler investigated polynomials , , , etc. (see the facsimile). These polynomials are a shifted form of what are now called the Eulerian polynomials ''A''_''n''(''x'').

Basic properties

For a given value of ''n'' > 0, the index ''m'' in ''A''(''n'', ''m'') can take values from 0 to ''n'' − 1. For fixed ''n'' there is a single permutation which has 0 ascents: (''n'', ''n'' − 1, ''n'' − 2, ..., 1). There is also a single permutation which has ''n'' − 1 ascents; this is the rising permutation (1, 2, 3, ..., ''n''). Therefore ''A''(''n'', 0) and ''A''(''n'', ''n'' − 1) are 1 for all values of ''n''.

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

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

:

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

:$A(n,m)=(n-m)A(n-1,m-1) + (m+1)A(n-1,m).$

For example

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

Values of ''A''(''n'', ''m'') for 0 ≤ ''n'' ≤ 9 are:

:

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''!.

Explicit formula

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

:$A(n,m)=\sum_^(-1)^k \binom (m+1-k)^n.$

One can see from this formula, as well as from the combinatorial interpretation, that $A(n,n) = 0$ for $n>0$, so that $A_(t)$ is a polynomial of degree $n-1$ for $n>0$.

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

:$\sum_^A(n,m)=n! \textn \ge 1.$

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

:$\sum_^(-1)^A(n,m)=\frac \textn \ge 1.$

Other summation properties of the Eulerian numbers are:

:$\sum_^(-1)^m\frac=0 \textn \ge 2,$

:$\sum_^(-1)^m\frac=(n+1)B_ \textn \ge 2,$

where ''B''_''n'' is the ''n''^th Bernoulli number.

Identities

The Eulerian numbers are involved in the generating function for the sequence of ''n''^th powers:
:$\sum_^k^n x^k = \frac = \frac$
for $n \geq 0$. This assumes that 0⁰ = 0 and ''A''(0,0) = 1 (since there is one permutation of no elements, and it has no ascents).

Worpitzky's identity expresses ''x''^''n'' as the linear combination of Eulerian numbers with binomial coefficients:
:$x^n=\sum_^A(n,m)\binom.$

It follows from Worpitzky's identity that
:$\sum_^k^n=\sum_^A(n,m)\binom.$

Another interesting identity is
:$\frac=\sum_^\infty\frac.$
The numerator on the right-hand side is the Eulerian polynomial.

For a fixed function $f: \mathbb \rightarrow \mathbb$ which is integrable on $(0, n)$ we have the integral formula Exercise 6.65 in ''Concrete Mathematics'' by Graham, Knuth and Patashnik.

:$\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.$

Eulerian numbers of the second order

The permutations of the multiset 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 order, denoted $\scriptstyle \left\langle \! \left\langle \right\rangle \! \right\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:

:$\left\langle \!\! \left\langle \right\rangle \!\! \right\rangle = (2n-m-1) \left\langle \!\! \left\langle \right\rangle \!\! \right\rangle + (m+1) \left\langle \!\! \left\langle \right\rangle \!\! \right\rangle,$

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

: \left\langle \!\! \left\langle \right\rangle \!\! \right\rangle = =0

Correspondingly, the Eulerian polynomial of second order, here denoted ''P''_''n'' (no standard notation exists for them) are

:$P_n(x) := \sum_^n \left\langle \!\! \left\langle \right\rangle \!\! \right\rangle x^m$

and the above recurrence relations are translated into a recurrence relation for the sequence ''P''_''n''(''x''):

:$P_(x) = (2nx+1) P_n(x) - x(x-1) P_n^\prime(x)$

with initial condition

:$P_0(x) = 1.$

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

:$(x-1)^ P_(x) = \left( x(1-x)^ P_n(x) \right)^\prime$

so that the rational function

:$u_n(x) := (x-1)^ P_(x)$

satisfies a simple autonomous recurrence:

:$u_ = \left( \frac u_n \right)^\prime, \quad u_0=1,$

whence one obtains the Eulerian polynomials of second order as ''P''_''n''(''x'') = (1−''x'')^2''n'' ''u''_''n''(''x''), and the Eulerian numbers of second order as their coefficients.

Here are some values of the second order Eulerian numbers:

:
The sum of the ''n''-th row, which is also the value ''P''_''n''(1), is (2''n'' − 1)!!.

Indexing the second-order Eulerian numbers comes in three flavors: following Riordan and Comtet, following Graham, Knuth, and Patashnik and , extending the definition of Gessel and Stanley.

References

* Eulerus, Leonardus eonhard Euler(1755). ''Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum oundations of differential calculus, with applications to finite analysis and series'. Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
*
*
*
*
*
*
*

*
*
*

Citations

External links

Eulerian Polynomials
at OEIS Wiki.
*
*
*
*
*{{MathWorld, title=Second-Order Eulerian Triangle, urlname=Second-OrderEulerianTriangle
Euler-matrix
(generalized rowindexes, divergent summation)

Enumerative combinatorics
Factorial and binomial topics
Integer sequences
Triangles of numbers