Eulerian number
In combinatorics, the Eulerian number \langle n \ k \rangle counts the number of permutations of the set \{1, 2, \dots, n\} with exactly k descents, where a descent is a position i (with $1 \leq i < n) such that the i-th entry exceeds the (i+1)-th entry in the permutation.[1] These nonnegative integers form a triangular array, with entries for fixed n ranging from k=0 to k=n-1, and they satisfy \sum_{k=0}^{n-1} \langle n \ k \rangle = n!, accounting for all permutations of n elements.[1] Introduced by Leonhard Euler in his 1755 treatise Institutiones calculi differentialis, the numbers initially arose in the context of differential calculus and series expansions but later found profound combinatorial interpretations.[2][1] The Eulerian numbers exhibit symmetry, with \langle n \ k \rangle = \langle n \ n-1-k \rangle, reflecting a bijection between permutations with k descents and those with n-1-k descents via reversal.[1] They obey the recurrence \langle n \ k \rangle = (k+1)\langle n-1 \ k \rangle + (n-k)\langle n-1 \ k-1 \rangle for $1 \leq k \leq n-1, with base cases \langle n \ 0 \rangle = 1 and \langle n \ k \rangle = 0 if k < 0 or k \geq n.[1] A key identity, Worpitzky's theorem, expresses powers as \sum_{k=0}^{n-1} \langle n \ k \rangle \binom{x+n-k-1}{n} = x^n for integer x \geq 1, linking the numbers to binomial expansions.[1] Eulerian polynomials A_n(x) = \sum_{k=0}^{n-1} \langle n \ k \rangle x^{k+1} encode these coefficients and appear in generating functions for permutation statistics, with the exponential generating function \sum_{n \geq 0} A_n(x) \frac{t^n}{n!} = \frac{1-x}{e^{t(x-1)} - x}.[1] Beyond enumerative combinatorics, Eulerian numbers connect to algebraic structures like the ring of quasi-symmetric functions, geometric interpretations in polytopes such as the Eulerian poset, and applications in dynamical systems and sorting algorithms.[1] Their study continues in modern research, including generalizations to q-analogues and multivariate extensions.[1]Fundamentals
Definition
The Eulerian numbers were first studied by Leonhard Euler in 1749 in the context of enumerating permutations, with the results appearing in print in his 1768 paper published in the Novi Commentarii Academiae Scientiarum Petropolitanae.[3][4] The Eulerian number A(n,k), also commonly denoted by the angle bracket notation \langle n \atop k \rangle or sometimes E(n,k), counts the number of permutations \pi of the set \{1, 2, \dots, n\} that have exactly k descents. A descent in a permutation \pi occurs at a position i (where $1 \leq i < n) if \pi(i) > \pi(i+1). These numbers are defined for positive integers n \geq 1 and integers k satisfying $0 \leq k \leq n-1. For instance, A(1,0) = 1 since the single permutation of \{1\} has no possible descents, while for n=2, A(2,0) = 1 (the increasing permutation (1,2)) and A(2,1) = 1 (the decreasing permutation (2,1)).[5] The Eulerian polynomials provide a generating function perspective on these numbers and are defined by A_n(x) = \sum_{k=0}^{n-1} A(n,k) \, x^k for n \geq 1, with A_0(x) = 1 by convention. The exponential generating function for the sequence of Eulerian polynomials is \sum_{n=0}^\infty A_n(x) \frac{t^n}{n!} = \frac{1-x}{e^{t(x-1)} - x}. Evaluating at x=1 yields A_n(1) = n!, reflecting the total count of permutations of n elements.[5] The initial values of the Eulerian numbers form a symmetric triangle, as shown below for n up to 5:| n \ k | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | 1 | 1 | |||
| 3 | 1 | 4 | 1 | ||
| 4 | 1 | 11 | 11 | 1 | |
| 5 | 1 | 26 | 66 | 26 | 1 |
Basic Properties
The Eulerian numbers A(n,k) satisfy the boundary conditions A(n,0) = 1 and A(n,n-1) = 1 for all integers n \geq 1, with A(n,k) = 0 whenever k < 0 or k \geq n.[7] These conditions follow directly from the combinatorial interpretation, as there is exactly one permutation of $$ with no descents (the increasing permutation) and exactly one with the maximum number of descents (the decreasing permutation).[8] A key structural feature is the symmetry relation A(n,k) = A(n, n-k-1) for $0 \leq k \leq n-1.[9] This reflection property arises from the bijection between permutations with k descents and those with n-1-k descents, obtained by reversing the order of the elements. The symmetry extends to the associated Eulerian polynomials A_n(x) = \sum_{k=0}^{n-1} A(n,k) x^k, which are palindromic of degree n-1, satisfying A_n(x) = x^{n-1} A_n(1/x).[8] Consequently, the coefficients of A_n(x) are positive integers, reflecting the strict positivity of the Eulerian numbers: A(n,k) > 0 for all $0 \leq k \leq n-1.[8] Regarding growth, for fixed k, the Eulerian numbers exhibit exponential behavior A(n,k) \sim (k+1)^n as n \to \infty.[9] This asymptotic follows from the explicit representation A(n,k) = \sum_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k+1-j)^n, where the dominant term is (k+1)^n.[9]Computation
Recurrence Relations
The Eulerian numbers \langle n \ k \rangle satisfy the fundamental recurrence relation \langle n \ k \rangle = (k+1) \langle n-1 \ k \rangle + (n-k) \langle n-1 \ k-1 \rangle for $1 \leq k \leq n-1, with boundary conditions \langle n \ 0 \rangle = 1 and \langle n \ n-1 \rangle = 1 for all n \geq 1.[10] This relation allows iterative computation by building values from previous rows, reflecting the combinatorial structure of permutations where the position of n in a permutation of \{1,2,\dots,n\} determines how descents are inherited from permutations of \{1,2,\dots,n-1\}. To compute the Eulerian numbers, one constructs the Eulerian triangle row by row starting from the base case n=1: \langle 1 \ 0 \rangle = 1. For subsequent rows, apply the recurrence with the boundaries. The values for small n are as follows:| n | k=0 | k=1 | k=2 | k=3 |
|---|---|---|---|---|
| 1 | 1 | |||
| 2 | 1 | 1 | ||
| 3 | 1 | 4 | 1 | |
| 4 | 1 | 11 | 11 | 1 |
Explicit Formulas
One of the primary explicit formulas for the Eulerian number \langle n \ k \rangle is the alternating summation \langle n \ k \rangle = \sum_{i=0}^{k+1} (-1)^i \binom{n+1}{i} (k+1 - i)^n, which arises from inclusion-exclusion principles applied to counting permutations with a fixed number of ascents or descents. This expression allows direct computation for any n and k without relying on smaller values and is particularly useful for asymptotic analysis or symbolic manipulation.[5] An equivalent reindexing of the sum, obtained by substituting j = k + 1 - i, yields \langle n \ k \rangle = \sum_{j=0}^{k+1} (-1)^{k+1-j} \binom{n+1}{k+1-j} j^n. This form bears a close resemblance to the explicit summation for the unsigned Stirling numbers of the second kind S(n+1, k+1) = \frac{1}{(k+1)!} \sum_{j=0}^{k+1} (-1)^{k+1-j} \binom{k+1}{j} j^{n+1}, highlighting structural parallels between the two sequences in expressing rising factorials or powers via signed sums; both originate from combinatorial inclusion-exclusion but differ in the binomial coefficients and scaling.[5] An integral representation provides another closed-form avenue for evaluation, given by \langle n \ k \rangle = \frac{1}{\pi} \int_0^\pi (\sin t)^{n+1} \cos \bigl( (n + 1 - 2k) t \bigr) \, dt for integers n \geq 0 and any integer k, with \langle n \ k \rangle = 0 outside $0 \leq k \leq n-1. This trigonometric integral facilitates connections to Fourier analysis and symmetric properties of Eulerian numbers, such as \langle n \ k \rangle = \langle n \ n - k - 1 \rangle.[11] Eulerian numbers can also be extracted via inversion of their generating function. The exponential generating function for the Eulerian polynomials A_n(y) = \sum_{k=0}^{n-1} \langle n \ k \rangle y^{k+1} is \sum_{n=0}^\infty A_n(y) \frac{x^n}{n!} = \frac{1-y}{e^{x(y-1)} - y}; thus, \langle n \ k \rangle = n! [x^n y^{k+1}] \frac{1-y}{e^{x(y-1)} - y}, where [ \cdot ] denotes the coefficient operator, offering a formal explicit expression through series expansion without summation over binomial terms.Identities
Summation Identities
One fundamental summation identity for the Eulerian numbers \langle n \ k \rangle is the total sum over the number of descents: \sum_{k=0}^{n-1} \langle n \ k \rangle = n!. This identity follows directly from the combinatorial interpretation of the Eulerian numbers, where \langle n \ k \rangle counts the permutations of = \{1, 2, \dots, n\} with exactly k descents (positions i where \pi_i > \pi_{i+1}). Since the sets of permutations partitioned by the number of descents (from 0 to n-1) cover all elements of the symmetric group S_n, the sum equals |S_n| = n!. A bijection establishing this is the identity map on S_n, which preserves the descent statistic while partitioning the group.[12] Partial sums of Eulerian numbers also admit a direct combinatorial interpretation. Specifically, \sum_{k=0}^m \langle n \ k \rangle counts the number of permutations in S_n with at most m descents, for $0 \leq m \leq n-1. This follows by summing the sizes of the disjoint sets of permutations with exactly k descents for k = 0 to m. While no simple closed form exists beyond this count, the partial sum provides insight into the distribution of descent statistics in S_n.[12] A weighted summation identity arises from probabilistic considerations of descents. The sum \sum_{k=0}^{n-1} k \, \langle n \ k \rangle = \frac{n-1}{2} \, n! equals n! times the expected number of descents in a uniform random permutation of . This expectation is computed via linearity: the number of descents is $\sum_{i=1}^{n-1} I_i$, where $I_i = 1$ if $\pi_i > \pi_{i+1}$ and 0 otherwise. Each $\mathbb{E}[I_i] = \Pr(\pi_i > \pi_{i+1}) = 1/2$, since the values at positions $i$ and $i+1$ form a random pair of distinct elements from , equally likely to be in either order. Thus, the total expectation is (n-1)/2. Equivalently, \sum_{k=0}^{n-1} (k+1) \, \langle n \ k \rangle = \frac{n+1}{2} \, n!, obtained by adding the total sum identity. This weighted sum highlights the central tendency of the descent distribution.[12] The Eulerian numbers satisfy a compact exponential generating function that encapsulates many summation properties: \sum_{n \geq 0} A_n(y) \frac{t^n}{n!} = \frac{1-y}{e^{t(y-1)} - y}, where A_n(y) = \sum_{k=0}^{n-1} \langle n \ k \rangle y^{k+1} is the Eulerian polynomial. This generating function arises from the recurrence \langle n \ k \rangle = (k+1) \langle n-1 \ k \rangle + (n-k) \langle n-1 \ k-1 \rangle. Setting A_0(y) = 1 and solving the corresponding differential equation yields the closed form, which encodes sums over both n and k.[12]Polynomial Identities
One of the central polynomial identities involving Eulerian numbers is Worpitzky's identity, established by Julius Worpitzky in 1883. It provides a representation of the power x^n as x^n = \sum_{k=0}^{n-1} \langle n \ k \rangle \binom{x + k}{n}, where the coefficients \langle n \ k \rangle are the Eulerian numbers. This identity highlights the role of Eulerian numbers in bridging the monomial basis and a shifted binomial basis in the vector space of polynomials of degree at most n. A combinatorial proof outlines the equivalence by interpreting the right-hand side as counting functions from an n-element set to an x-element set via permutations with k descents: the Eulerian number \langle n \ k \rangle enumerates such permutations of $$, while \binom{x + k}{n} counts the ways to assign increasing labels from a multiset of size x + k to the descent blocks, yielding the total x^n functions overall.[13][1] The inverse relation to Worpitzky's identity expresses shifted binomial coefficients in terms of powers, weighted by signed Eulerian numbers, and is derived via inclusion-exclusion. Substituting the explicit inclusion-exclusion formula for the Eulerian numbers, \langle n \ k \rangle = \sum_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k + 1 - j)^n, into the Worpitzky identity and rearranging yields an expression for \binom{x + k}{n} as an alternating sum involving powers y^m with coefficients depending on Eulerian numbers, confirming the triangular invertibility of the transformation matrix. This inclusion-exclusion approach underscores the combinatorial overcounting and correction inherent in descent statistics.[1] A related congruence is the Touchard congruence, stating that for n > 1, \sum_{k=0}^{n-1} \langle n \ k \rangle \equiv 0 \pmod{n}. Since the sum equals n!, which is divisible by n for n > 1, this provides a modular arithmetic perspective on the total count of permutations.[14] Eulerian numbers connect to tangent numbers (the odd-indexed Euler-Bernoulli numbers) through evaluation of the Eulerian polynomial A_n(x) = \sum_{k=0}^{n-1} \langle n \ k \rangle x^{k+1} at x = -1. For odd n, A_n(-1) = (-1)^{(n+1)/2} E_n, where E_n counts the number of alternating permutations of $$. This correspondence arises from generating function identities linking Eulerian polynomials to the Taylor series of \tan x.[15]Alternating Sum Formulas
One key alternating sum involving Eulerian numbers \langle n \ k \rangle, which count the number of permutations of with exactly $k$ descents, is the evaluation of the Eulerian polynomial $A_n(x) = \sum_{k=0}^{n-1} \langle n \ k \rangle x^{k+1}$ at $x = -1$. This yields $A_n(-1) = \sum_{k=0}^{n-1} \langle n \ k \rangle (-1)^{k+1} = 0$ when $n$ is even, reflecting a perfect cancellation in the signed enumeration of permutations by the number of descents. For odd $n$, the value equals $(-1)^{(n+1)/2} E_n$, where $E_n$ is the $n$-th Euler zigzag number, counting the number of alternating permutations of. This connection arises from combinatorial bijections and generating function evaluations, linking the signed descent statistic to up-down permutation structures.[16][12] The explicit formula for individual Eulerian numbers also involves an alternating sum derived from the principle of inclusion-exclusion applied to descent positions. Specifically, \langle n \ k \rangle = \sum_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k + 1 - j)^n. This expression counts permutations with exactly k descents by overcounting those with descents forced at certain positions and correcting via inclusion-exclusion on the excess descents. The alternating signs account for the over- and under-counts in the union of sets where specific potential descent positions are designated. This approach parallels the inclusion-exclusion formula for derangements !n = n! \sum_{j=0}^n \frac{(-1)^j}{j!}, where fixed points play the role analogous to descents, providing a refined signed count in permutation statistics.[12] Summing the explicit formula over k with alternating signs recovers the evaluation A_n(-1), as interchanging sums leads to a double alternating sum that simplifies via generating functions or direct computation. In the context of signed permutations, this alternating sum interprets as the Euler characteristic of certain permutation posets or the signed trace over descent operators, extending to type B Eulerian numbers where signs incorporate inversion statistics.[16][12] The connection to forward differences emerges in the explicit formula, where the sum \sum_{j} (-1)^j \binom{n+1}{j} f(k+1-j) resembles the forward difference operator \Delta^{n+1} f(y) = \sum_{j=0}^{n+1} (-1)^j \binom{n+1}{j} f(y - j) evaluated at appropriate points, with f(y) = y^n. This operator perspective frames Eulerian numbers as coefficients in the finite difference expansion of monomials, bridging combinatorial counts to umbral calculus and polynomial interpolation. For example, the identity aligns with representations where \Delta^n 0^m for m \geq n involves Stirling numbers, but the Eulerian form refines the descent-based refinement.[16][12]| n | A_n(-1) | Interpretation |
|---|---|---|
| 1 | -1 | (-1)^{(1+1)/2} E_1 = -1 |
| 2 | 0 | Even n |
| 3 | 2 | (-1)^{(3+1)/2} E_3 = 2 |
| 4 | 0 | Even n |
| 5 | -16 | (-1)^{(5+1)/2} E_5 = -16 |