Eulerian number


In combinatorics, the Eulerian number is the number of permutations of the numbers 1 to ' in which exactly ' elements are greater than the previous element.
Leonhard Euler investigated them and associated polynomials in his 1755 book Institutiones calculi differentialis. He first studied them in 1749.
[Image:EulerianPolynomialsByEuler1755.png|right|303px|thumb|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 numbers.]
Other notations for are and.

Definition

The Eulerian polynomials are defined by the exponential generating function
The Eulerian numbers may also be defined as the coefficients of the Eulerian polynomials:
An explicit formula for is

Basic properties

  • For fixed ' there is a single permutation which has 0 ascents:. Indeed, as for all,. This formally includes the empty collection of numbers,. And so.
  • For the explicit formula implies, a sequence in that reads.
  • Fully reversing a permutation with ' ascents creates another permutation in which there are ' ascents. Therefore. So there is also a single permutation which has ' ascents, namely the rising permutation. So also equals.
  • Since a permutation of the numbers to which has ascents must have descents, the symmetry shows that also counts the number of permutations with descents.
  • For, the values are formally zero, meaning many sums over can be written with an upper index only up to. It also means that the polynomials are really of degree for.
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 for are:

Computation

For larger values of, can also be calculated using the recursive formula
This formula can be motivated from the combinatorial definition and thus serves as a natural starting point for the theory.
For small values of ' and ', the values of can be calculated by hand. For example
Applying the recurrence to one example, we may find
Likewise, the Eulerian polynomials can be computed by the recurrence
The second formula can be cast into an inductive form,

Identities

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 elements, so their sum equals the factorial. I.e.
as well as. To avoid conflict with the empty sum convention, it is convenient to simply state the theorems for only.
Much more generally, for a fixed function integrable on the interval
Worpitzky's identity expresses as the linear combination of Eulerian numbers with binomial coefficients:
From this, it follows that
They appear as the coefficients of the polylogarithm.

Formulas involving alternating sums

The alternating sum of the Eulerian numbers for a fixed value of is related to the Bernoulli number
Furthermore,
and

Formulas involving the polynomials

The symmetry property implies:
The Eulerian numbers are involved in the generating function for the sequence of nth powers:
An explicit expression for Eulerian polynomials is
where is the Stirling number of the second kind.

Geometric interpretations

The Eulerian numbers have two important geometric interpretations involving convex polytopes.
First of all, the identity
implies that the Eulerian numbers form the -vector of the standard -dimensional hypercube, which is the convex hull of all -vectors in.
Secondly, the identity
means that the Eulerian numbers also form the -vector of the simple polytope which is dual to the -dimensional permutohedron, which is the convex hull of all permutations of the vector in.
In fact, as explained by Richard Stanley in an, these two geometric guises of the Eulerian numbers are closely linked.

Type B Eulerian numbers

The hyperoctahedral group of order is the group of all signed permutations of the numbers to, meaning bijections from the set to itself with the property that for all. Just as the symmetric group of order is the Coxeter group of Type, the hyperoctahedral group of order is the Coxeter group of Type.
Given an element of the hyperoctahedral group of order a Type B descent of is an index for which, with the convention that. The Type B Eulerian number is the number of elements of the hyperoctahedral group of order with exactly descents; see Chow and Gessel.
The table of is
The corresponding polynomials are called midpoint Eulerian polynomials because of their use in interpolation and spline theory; see Schoenberg.
The Type B Eulerian numbers and polynomials satisfy many similar identities, and have many similar properties, as the Type A, i.e., usual, Eulerian numbers and polynomials. For example, for any,
And the Type B Eulerian numbers give the h-vector of the simple polytope dual to the Type B permutohedron.
In fact, one can define Eulerian numbers for any finite Coxeter group with analogous properties: see part III of the textbook of Petersen in the references.

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. These are called Stirling permutations.
The Eulerian number of the second order, denoted, counts the number of all such Stirling 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:
The Eulerian numbers of the second order satisfy the recurrence relation, that follows directly from the above definition:
with initial condition for n = 0, expressed in Iverson bracket notation:
Correspondingly, the Eulerian polynomial of second order, here denoted Pn are
and the above recurrence relations are translated into a recurrence relation for the sequence Pn:
with initial condition. The latter recurrence may be written in a somewhat more compact form by means of an integrating factor:
so that the rational function
satisfies a simple autonomous recurrence:
Whence one obtains the Eulerian polynomials of second order as, and the Eulerian numbers of second order as their coefficients.
The Eulerian polynomials of the second order satisfy an identity analogous to the identity
satisfied by the usual Eulerian polynomials. Specifically, as proved by Gessel and Stanley, they satisfy the identity
where again the denote the Stirling numbers of the second kind.
The following table displays the first few second-order Eulerian numbers:
The sum of the n-th row, which is also the value, is.
Indexing the second-order Eulerian numbers comes in three flavors:
  • following Riordan and Comtet,
  • following Graham, Knuth, and Patashnik,
  • , extending the definition of Gessel and Stanley.