Eulerian number
In combinatorics, the Eulerian number
elements are greater than the previous element (permutations with
Leonhard Euler investigated them and associated polynomials in his 1755 book Institutiones calculi differentialis.
are defined by the exponential generating function The Eulerian numbers
may be defined as the coefficients of the Eulerian polynomials: An explicit formula for
is[1] 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.
(sequence A008292 in the OEIS) for
are: For larger values of
can also be calculated using the recursive formula[2] This formula can be motivated from the combinatorial definition and thus serves as a natural starting point for the theory.
For small values of
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, 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
To avoid conflict with the empty sum convention, it is convenient to simply state the theorems for
Much more generally, for a fixed function
integrable on the interval
[3] Worpitzky's identity[4] expresses
as the linear combination of Eulerian numbers with binomial coefficients: From it, it follows that The alternating sum of the Eulerian numbers for a fixed value of
is related to the Bernoulli number
Furthermore, and 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[5]
is the Stirling number of the second kind.
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
The Eulerian number of the second order, denoted
, 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: 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 (no standard notation exists for them) are and the above recurrence relations are translated into a recurrence relation for the sequence Pn(x): 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 following table displays the first few second-order Eulerian numbers: The sum of the n-th row, which is also the value
Indexing the second-order Eulerian numbers comes in three flavors:
