Eulerian number

The Eulerian polynomials A_n(t) are defined by the exponential generating function :\sum_{n=0}^{\infty} A_{n}(t) \,\frac{x^n}{n!} = \frac{t-1}{t - e^{(t-1)\,x}} = \left(1-\frac{e^{(t-1)x}-1}{t-1}\right)^{-1}. The Eulerian numbers A(n,k) may also be defined as the coefficients of the Eulerian polynomials: :A_{n}(t) = \sum_{k=0}^n A(n,k)\,t^k. An explicit formula for A(n,k) is :A(n,k)=\sum_{i=0}^{k}(-1)^i \binom{n+1}{i} (k+1-i)^n. ==Basic properties== • For fixed n there is a single permutation which has 0 ascents: (n, n-1, n-2, \ldots, 1). Indeed, as {\tbinom n 0}=1 for all n, A(n, 0) = 1. This formally includes the empty collection of numbers, n=0. And so A_0(t)=A_1(t)=1. • For k=1 the explicit formula implies A(n,1)=2^n-(n+1), a sequence in n that reads 0, 0, 1, 4, 11, 26, 57, \dots. • Fully reversing a permutation with k ascents creates another permutation in which there are n-k-1 ascents. Therefore A(n, k) = A(n, n-k-1). So there is also a single permutation which has n-1 ascents, namely the rising permutation (1, 2, \ldots, n). So also A(n, n-1) equals 1. • Since a permutation of the numbers 1 to n which has k ascents must have n-1-k descents, the symmetry A(n, k) = A(n, n-k-1) shows that A(n, k) also counts the number of permutations with k descents. • For k\ge n > 0, the values are formally zero, meaning many sums over k can be written with an upper index only up to n-1. It also means that the polynomials A_{n}(t) are really of degree n-1 for n>0. 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 A(n, k) for 0 \le n \le 9 are: : ==Computation==

For larger values of n, A(n,k) can also be calculated using the recursive formula :A(n,k)=(n-k)\,A(n-1,k-1) + (k+1)\,A(n-1,k). This formula can be motivated from the combinatorial definition and thus serves as a natural starting point for the theory. For small values of n and k, the values of A(n,k) can be calculated by hand. For example : Applying the recurrence to one example, we may find :A(4,1)=(4-1)\,A(3,0) + (1+1)\,A(3,1)=3 \cdot 1 + 2 \cdot 4 = 11. Likewise, the Eulerian polynomials can be computed by the recurrence :A_{0}(t) = 1, :A_{n}(t) = A_{n-1}'(t)\cdot t\,(1-t) + A_{n-1}(t)\cdot (1+(n-1)\,t),\text{ for } n > 1. The second formula can be cast into an inductive form, :A_{n}(t) = \sum_{k=0}^{n-1} \binom{n}{k} A_{k}(t)\cdot (t-1)^{n-1-k}, \text{ for } n > 1. ==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 n elements, so their sum equals the factorial n!: \sum_{k=0}^{n} A(n,k) = n! \,. (The summand k = n is 0 for n>0, but is included to give the correct sum A(0,0)=0! when n = 0.) Much more generally, for a fixed function f\colon \mathbb{R} \rightarrow \mathbb{C} integrable on the interval (0, n) :\sum_{k=0}^{n-1} A(n, k)\, f(k) = n!\int_0^1 \cdots \int_0^1 f\left(\left\lfloor x_1 + \cdots + x_n\right\rfloor\right) {\mathrm d}x_1 \cdots {\mathrm d}x_n '''Worpitzky's identity''' (in fact, before Worpitzky, this identity was already contained in Li Shanlan's Duò Jī Bǐ Lèi, which was published in 1867) expresses x^n as the linear combination of Eulerian numbers with binomial coefficients: :\sum_{k=0}^{n-1}A(n,k)\binom{x+k}{n}=x^n. From this, it follows that :\sum_{k=1}^{m}k^n=\sum_{k=0}^{n-1} A(n,k) \binom{m+k+1}{n+1}. Eulerian numbers appear as the coefficients of the polylogarithm for negative integer inputs:\operatorname{Li}_{-n}(z) = {1 \over (1-z)^{n+1}} \sum_{k=0}^{n-1} A(n, k) z^{n-k} \qquad (n=1,2,3,\ldots). Formulas involving alternating sums The alternating sum of the Eulerian numbers for a fixed value of n is related to the Bernoulli number B_{n+1} :\sum_{k=0}^{n-1}(-1)^k A(n,k) = 2^{n+1}(2^{n+1}-1) \frac{B_{n+1}}{n+1}, \text{ for }n > 0. Furthermore, :\sum_{k=0}^{n-1}(-1)^k \frac{A(n,k)}{\binom{n-1}{k}}=0, \text{ for }n > 1 and :\sum_{k=0}^{n-1}(-1)^k \frac{A(n,k)}{\binom{n}{k}}=(n+1)B_{n}, \text{ for } n > 1 Formulas involving the polynomials The symmetry property implies: :A_n(t) = t^{n-1} A_n(t^{-1}) The Eulerian numbers are involved in the generating function for the sequence of nth powers: :\sum_{i=1}^\infty i^n x^i = \frac{1}{(1-x)^{n+1}}\sum_{k=0}^n A(n,k)\,x^{k+1} = \frac{x}{(1-x)^{n+1}}A_n(x) An explicit expression for Eulerian polynomials is A_n(t) = \sum_{k=0}^n \left\{ {n \atop k} \right\} k! (t-1)^{n-k} where \left\{ {n \atop k} \right\} 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 :\sum_{i=0}^\infty (i+1)^n x^i = \frac{1}{(1-x)^{n+1}}\sum_{k=0}^n A(n,k)\,x^{k} implies that the Eulerian numbers form the h^\ast-vector of the standard n-dimensional hypercube, which is the convex hull of all 0,1-vectors in \mathbb{R}^n. Secondly, the identity A_n(t) = \sum_{k=0}^n \left\{ {n \atop k} \right\} k! (t-1)^{n-k} means that the Eulerian numbers also form the h-vector of the simple polytope which is dual to the n-dimensional permutohedron, which is the convex hull of all permutations of the vector (1,2,\ldots,n) in \mathbb{R}^n. ==Type B Eulerian numbers==

The hyperoctahedral group of order n is the group of all signed permutations of the numbers 1 to n, meaning bijections \pi from the set \{-n,-n+1,\ldots,-1,1,2,\ldots,n\} to itself with the property that \pi(-i)=-\pi(i) for all i. Just as the symmetric group of order n (i.e., the group of all permutations of the numbers 1 to n) is the Coxeter group of Type A_{n-1}, the hyperoctahedral group of order n is the Coxeter group of Type B_n. Given an element \pi of the hyperoctahedral group of order n a Type B descent of \pi is an index i \in \{0,1,\ldots,n-1\} for which \pi(i) > \pi(i-1), with the convention that \pi(0)=0. The Type B Eulerian number B(n,k) is the number of elements of the hyperoctahedral group of order n with exactly k descents; see Chow and Gessel. The table of B(n,k) (sequence A060187 in the OEIS) is : The corresponding polynomials M_n(x) = \sum_{k=0}^{n}B(n,k)x^k 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 n \geq 1, :\sum_{i=0}^{\infty}(2i+1)^nx^i = \frac{M_{n}(x)}{(1-x)^{n+1}}. 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 \{1, 1, 2, 2, \ldots, n, n\} 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 (2n-1)!!. These are called Stirling permutations. The Eulerian number of the second order, denoted \left\langle \! \left\langle {n \atop m} \right\rangle \! \right\rangle , 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: : 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 {n \atop k} \right\rangle \!\! \right\rangle = (2n-k-1) \left\langle \!\! \left\langle {n-1 \atop k-1} \right\rangle \!\! \right\rangle + (k+1) \left\langle \!\! \left\langle {n-1 \atop k} \right\rangle \!\! \right\rangle, with initial condition for n = 0, expressed in Iverson bracket notation: : \left\langle \!\! \left\langle {0 \atop k} \right\rangle \!\! \right\rangle = [k=0]. Correspondingly, the Eulerian polynomial of second order, here denoted Pn (no standard notation exists for them) are :P_n(x) := \sum_{k=0}^n \left\langle \!\! \left\langle {n \atop k} \right\rangle \!\! \right\rangle x^k and the above recurrence relations are translated into a recurrence relation for the sequence Pn(x): : P_{n+1}(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 somewhat more compact form by means of an integrating factor: : (x-1)^{-2n-2} P_{n+1}(x) = \left( x\,(1-x)^{-2n-1} P_n(x) \right)^\prime so that the rational function : u_n(x) := (x-1)^{-2n} P_{n}(x) satisfies a simple autonomous recurrence: : u_{n+1} = \left( \frac{x}{1-x} u_n \right)^\prime, \quad u_0=1 Whence one obtains the Eulerian polynomials of second order as P_n(x) = (1-x)^{2n} u_n(x), and the Eulerian numbers of second order as their coefficients. The Eulerian polynomials of the second order satisfy an identity analogous to the identity :\sum_{i=1}^\infty i^n x^i = \frac{xA_n(x)}{(1-x)^{n+1}} satisfied by the usual Eulerian polynomials. Specifically, as proved by Gessel and Stanley, they satisfy the identity :\sum_{m=0}^{\infty}\left\{ {n+m \atop m} \right\}x^m = \frac{xP_n(x)}{(1-x)^{2n+1}} where again the \left\{ {n \atop k} \right\} denote the Stirling numbers of the second kind. (This appearance of the Stirling numbers explains the terminology "Stirling permutations.") The following table displays the first few second-order Eulerian numbers: : The sum of the n-th row, which is also the value P_n(1), is (2n-1)!!. 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. ==References==