Eulerian numbers

☆ Save On Wikipedia ↗

In combinatorics, the Eulerian number A ( n , k ) {\textstyle A(n,k)} {\textstyle A(n,k)} is the number of permutations of the numbers 1 to n {\textstyle n} {\textstyle n} in which exactly k {\textstyle k} {\textstyle k} elements are greater than the previous element (permutations with k {\textstyle k} {\textstyle k} "ascents").

Leonhard Euler investigated them and associated polynomials in his 1755 book Institutiones calculi differentialis.[1][2]

The polynomials presently known as Eulerian polynomials in Euler's work from 1755, Institutiones calculi differentialis, part 2, §173, p. 485/6. The coefficients of these polynomials are known as Eulerian numbers.

Other notations for A ( n , k ) {\textstyle A(n,k)} {\textstyle A(n,k)} are E ( n , k ) {\textstyle E(n,k)} {\textstyle E(n,k)} and ⟨ n k ⟩ {\displaystyle \textstyle \left\langle {n \atop k}\right\rangle } {\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }.

Definition

A plot of the Eulerian numbers with the second argument fixed to 5.
A plot of the Eulerian numbers with the second argument fixed to 5.

The Eulerian polynomials A n ( t ) {\displaystyle A_{n}(t)} {\displaystyle A_{n}(t)} are defined by the exponential generating function

∑ n = 0 ∞ A n ( t ) x n n ! = t − 1 t − e ( t − 1 ) x = ( 1 − e ( t − 1 ) x − 1 t − 1 ) − 1 . {\displaystyle \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}.} {\displaystyle \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 ) {\displaystyle A(n,k)} {\displaystyle A(n,k)} may also be defined as the coefficients of the Eulerian polynomials:

A n ( t ) = ∑ k = 0 n A ( n , k ) t k . {\displaystyle A_{n}(t)=\sum _{k=0}^{n}A(n,k)\,t^{k}.} {\displaystyle A_{n}(t)=\sum _{k=0}^{n}A(n,k)\,t^{k}.}

An explicit formula for A ( n , k ) {\textstyle A(n,k)} {\textstyle A(n,k)} is[3]

A ( n , k ) = ∑ i = 0 k ( − 1 ) i ( n + 1 i ) ( k + 1 − i ) n . {\displaystyle A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.} {\displaystyle A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.}

Basic properties

  • For fixed n {\textstyle n} {\textstyle n} there is a single permutation which has 0 ascents: ( n , n − 1 , n − 2 , … , 1 ) {\textstyle (n,n-1,n-2,\ldots ,1)} {\textstyle (n,n-1,n-2,\ldots ,1)}. Indeed, as ( n 0 ) = 1 {\displaystyle {\tbinom {n}{0}}=1} {\displaystyle {\tbinom {n}{0}}=1} for all n {\displaystyle n} {\displaystyle n}, A ( n , 0 ) = 1 {\textstyle A(n,0)=1} {\textstyle A(n,0)=1}. This formally includes the empty collection of numbers, n = 0 {\textstyle n=0} {\textstyle n=0}. And so A 0 ( t ) = A 1 ( t ) = 1 {\textstyle A_{0}(t)=A_{1}(t)=1} {\textstyle A_{0}(t)=A_{1}(t)=1}.
  • For k = 1 {\textstyle k=1} {\textstyle k=1} the explicit formula implies A ( n , 1 ) = 2 n − ( n + 1 ) {\textstyle A(n,1)=2^{n}-(n+1)} {\textstyle A(n,1)=2^{n}-(n+1)}, a sequence in n {\displaystyle n} {\displaystyle n} that reads 0 , 0 , 1 , 4 , 11 , 26 , 57 , … {\textstyle 0,0,1,4,11,26,57,\dots } {\textstyle 0,0,1,4,11,26,57,\dots }.
  • Fully reversing a permutation with k {\textstyle k} {\textstyle k} ascents creates another permutation in which there are n − k − 1 {\textstyle n-k-1} {\textstyle n-k-1} ascents. Therefore A ( n , k ) = A ( n , n − k − 1 ) {\textstyle A(n,k)=A(n,n-k-1)} {\textstyle A(n,k)=A(n,n-k-1)}. So there is also a single permutation which has n − 1 {\textstyle n-1} {\textstyle n-1} ascents, namely the rising permutation ( 1 , 2 , … , n ) {\textstyle (1,2,\ldots ,n)} {\textstyle (1,2,\ldots ,n)}. So also A ( n , n − 1 ) {\textstyle A(n,n-1)} {\textstyle A(n,n-1)} equals 1 {\displaystyle 1} {\displaystyle 1}.
  • Since a permutation of the numbers 1 {\displaystyle 1} {\displaystyle 1} to n {\displaystyle n} {\displaystyle n} which has k {\displaystyle k} {\displaystyle k} ascents must have n − 1 − k {\displaystyle n-1-k} {\displaystyle n-1-k} descents, the symmetry A ( n , k ) = A ( n , n − k − 1 ) {\textstyle A(n,k)=A(n,n-k-1)} {\textstyle A(n,k)=A(n,n-k-1)} shows that A ( n , k ) {\textstyle A(n,k)} {\textstyle A(n,k)} also counts the number of permutations with k {\displaystyle k} {\displaystyle k} descents.
  • For k ≥ n > 0 {\textstyle k\geq n>0} {\textstyle k\geq n>0}, the values are formally zero, meaning many sums over k {\textstyle k} {\textstyle k} can be written with an upper index only up to n − 1 {\textstyle n-1} {\textstyle n-1}. It also means that the polynomials A n ( t ) {\displaystyle A_{n}(t)} {\displaystyle A_{n}(t)} are really of degree n − 1 {\textstyle n-1} {\textstyle n-1} for n > 0 {\textstyle n>0} {\textstyle 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 ) {\textstyle A(n,k)} {\textstyle A(n,k)} (sequence A008292 in the OEIS) for 0 ≤ n ≤ 9 {\textstyle 0\leq n\leq 9} {\textstyle 0\leq n\leq 9} are:

 k
n 
 0 1 2 3 4 5 6 7 8
0 1
1 1
2 11
3 141
4 111111
5 12666261
6 157302302571
7 11201191241611911201
8 12474293156191561942932471
9 1502146088823415619088234146085021

Computation

For larger values of n {\textstyle n} {\textstyle n}, A ( n , k ) {\textstyle A(n,k)} {\textstyle A(n,k)} can also be calculated using the recursive formula[4]

A ( n , k ) = ( n − k ) A ( n − 1 , k − 1 ) + ( k + 1 ) A ( n − 1 , k ) . {\displaystyle A(n,k)=(n-k)A(n-1,k-1)+(k+1)A(n-1,k).} {\displaystyle 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 {\textstyle n} {\textstyle n} and k {\textstyle k} {\textstyle k}, the values of A ( n , k ) {\textstyle A(n,k)} {\textstyle A(n,k)} can be calculated by hand. For example

n k Permutations A(n, k)
1 0 (1) A(1,0) = 1
2 0 (2, 1) A(2,0) = 1
1 (1, 2) A(2,1) = 1
3 0 (3, 2, 1) A(3,0) = 1
1 (1, 3, 2), (2, 1, 3), (2, 3, 1) and (3, 1, 2) A(3,1) = 4
2 (1, 2, 3) A(3,2) = 1

Applying the recurrence to one example, we may find

A ( 4 , 1 ) = ( 4 − 1 ) A ( 3 , 0 ) + ( 1 + 1 ) A ( 3 , 1 ) = 3 ⋅ 1 + 2 ⋅ 4 = 11. {\displaystyle A(4,1)=(4-1)\,A(3,0)+(1+1)\,A(3,1)=3\cdot 1+2\cdot 4=11.} {\displaystyle 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 , {\displaystyle A_{0}(t)=1,} {\displaystyle A_{0}(t)=1,}
A n ( t ) = A n − 1 ′ ( t ) ⋅ t ( 1 − t ) + A n − 1 ( t ) ⋅ ( 1 + ( n − 1 ) t ) ,  for  n > 1. {\displaystyle A_{n}(t)=A_{n-1}'(t)\cdot t\,(1-t)+A_{n-1}(t)\cdot (1+(n-1)\,t),{\text{ for }}n>1.} {\displaystyle 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 ) = ∑ k = 0 n − 1 ( n k ) A k ( t ) ⋅ ( t − 1 ) n − 1 − k ,  for  n > 1. {\displaystyle A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}A_{k}(t)\cdot (t-1)^{n-1-k},{\text{ for }}n>1.} {\displaystyle 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 set partition of a finite set into disjoint subsets, the sum of the cardinalities of the parts equals the cardinality of the whole set. Since there are n ! {\displaystyle n!} {\displaystyle n!} (the factorial of n {\displaystyle n} {\displaystyle n}) permutations of size n {\displaystyle n} {\displaystyle n}, and the Eulerian numbers give the cardinalities of the subsets of these permutations with fixed number of descents, it follows that ∑ k = 0 n A ( n , k ) = n ! . {\displaystyle \sum _{k=0}^{n}A(n,k)=n!\,.} {\displaystyle \sum _{k=0}^{n}A(n,k)=n!\,.} (The summand k = n {\displaystyle k=n} {\displaystyle k=n} is 0 for n > 0 {\displaystyle n>0} {\displaystyle n>0}, but is included to give the correct sum A ( 0 , 0 ) = 0 ! {\displaystyle A(0,0)=0!} {\displaystyle A(0,0)=0!} when n = 0 {\displaystyle n=0} {\displaystyle n=0}.) Much more generally, for a fixed function f : R → C {\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {C} } {\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {C} } integrable on the interval [ 0 , n ] {\displaystyle [0,n]} {\displaystyle [0,n]}, the following identity holds:[5]

∑ k = 0 n − 1 A ( n , k ) f ( k ) = n ! ∫ 0 1 ⋯ ∫ 0 1 f ( ⌊ x 1 + ⋯ + x n ⌋ ) d x 1 ⋯ d x n . {\displaystyle \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)dx_{1}\cdots dx_{n}.} {\displaystyle \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)dx_{1}\cdots dx_{n}.}

Worpitzky's identity expresses x n {\textstyle x^{n}} {\textstyle x^{n}} as the linear combination of Eulerian numbers with binomial coefficients:

∑ k = 0 n − 1 A ( n , k ) ( x + k n ) = x n . {\displaystyle \sum _{k=0}^{n-1}A(n,k){\binom {x+k}{n}}=x^{n}.} {\displaystyle \sum _{k=0}^{n-1}A(n,k){\binom {x+k}{n}}=x^{n}.}

From this, it follows that

∑ k = 1 m k n = ∑ k = 0 n − 1 A ( n , k ) ( m + k + 1 n + 1 ) . {\displaystyle \sum _{k=1}^{m}k^{n}=\sum _{k=0}^{n-1}A(n,k){\binom {m+k+1}{n+1}}.} {\displaystyle \sum _{k=1}^{m}k^{n}=\sum _{k=0}^{n-1}A(n,k){\binom {m+k+1}{n+1}}.}

This identity is named after Julius Worpitzky, who discovered it in the 1880s;[6] it had been originally discovered somewhat earlier, by Li Shanlan in his 1867 work Duò Jī Bǐ Lèi.[7][8]

Eulerian numbers appear as the coefficients of the polylogarithm for negative integer inputs: Li − n ⁡ ( z ) = 1 ( 1 − z ) n + 1 ∑ k = 0 n − 1 A ( n , k ) z n − k ( n = 1 , 2 , 3 , … ) . {\displaystyle \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 ).} {\displaystyle \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 {\textstyle n} {\textstyle n} is related to the Bernoulli number B n + 1 {\textstyle B_{n+1}} {\textstyle B_{n+1}}

∑ k = 0 n − 1 ( − 1 ) k A ( n , k ) = 2 n + 1 ( 2 n + 1 − 1 ) B n + 1 n + 1 ,  for  n > 0. {\displaystyle \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.} {\displaystyle \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,

∑ k = 0 n − 1 ( − 1 ) k A ( n , k ) ( n − 1 k ) = 0 ,  for  n > 1 {\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k}}}=0,{\text{ for }}n>1} {\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k}}}=0,{\text{ for }}n>1}

and

∑ k = 0 n − 1 ( − 1 ) k A ( n , k ) ( n k ) = ( n + 1 ) B n ,  for  n > 1 {\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n}{k}}}=(n+1)B_{n},{\text{ for }}n>1} {\displaystyle \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 ) {\displaystyle A_{n}(t)=t^{n-1}A_{n}(t^{-1})} {\displaystyle 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:

∑ i = 1 ∞ i n x i = 1 ( 1 − x ) n + 1 ∑ k = 0 n A ( n , k ) x k + 1 = x ( 1 − x ) n + 1 A n ( x ) {\displaystyle \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)} {\displaystyle \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[9]

A n ( t ) = ∑ k = 0 n { n k } k ! ( t − 1 ) n − k {\displaystyle A_{n}(t)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}k!(t-1)^{n-k}} {\displaystyle A_{n}(t)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}k!(t-1)^{n-k}}

where { n k } {\textstyle \left\{{n \atop k}\right\}} {\textstyle \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

∑ i = 0 ∞ ( i + 1 ) n x i = 1 ( 1 − x ) n + 1 ∑ k = 0 n A ( n , k ) x k {\displaystyle \sum _{i=0}^{\infty }(i+1)^{n}x^{i}={\frac {1}{(1-x)^{n+1}}}\sum _{k=0}^{n}A(n,k)\,x^{k}} {\displaystyle \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 ∗ {\displaystyle h^{\ast }} {\displaystyle h^{\ast }}-vector of the standard n {\displaystyle n} {\displaystyle n}-dimensional hypercube, which is the convex hull of all 0 , 1 {\displaystyle 0,1} {\displaystyle 0,1}-vectors in R n {\displaystyle \mathbb {R} ^{n}} {\displaystyle \mathbb {R} ^{n}}.

Secondly, the identity A n ( t ) = ∑ k = 0 n { n k } k ! ( t − 1 ) n − k {\displaystyle A_{n}(t)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}k!(t-1)^{n-k}} {\displaystyle 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 {\displaystyle h} {\displaystyle h}-vector of the simple polytope which is dual to the n {\displaystyle n} {\displaystyle n}-dimensional permutohedron, which is the convex hull of all permutations of the vector ( 1 , 2 , … , n ) {\displaystyle (1,2,\ldots ,n)} {\displaystyle (1,2,\ldots ,n)} in R n {\displaystyle \mathbb {R} ^{n}} {\displaystyle \mathbb {R} ^{n}}.

Type B Eulerian numbers

The hyperoctahedral group of order n {\displaystyle n} {\displaystyle n} is the group of all signed permutations of the numbers 1 {\displaystyle 1} {\displaystyle 1} to n {\displaystyle n} {\displaystyle n}, meaning bijections π {\displaystyle \pi } {\displaystyle \pi } from the set { − n , − n + 1 , … , − 1 , 1 , 2 , … , n } {\displaystyle \{-n,-n+1,\ldots ,-1,1,2,\ldots ,n\}} {\displaystyle \{-n,-n+1,\ldots ,-1,1,2,\ldots ,n\}} to itself with the property that π ( − i ) = − π ( i ) {\displaystyle \pi (-i)=-\pi (i)} {\displaystyle \pi (-i)=-\pi (i)} for all i {\displaystyle i} {\displaystyle i}. Just as the symmetric group of order n {\displaystyle n} {\displaystyle n} (i.e., the group of all permutations of the numbers 1 {\displaystyle 1} {\displaystyle 1} to n {\displaystyle n} {\displaystyle n}) is the Coxeter group of Type A n − 1 {\displaystyle A_{n-1}} {\displaystyle A_{n-1}}, the hyperoctahedral group of order n {\displaystyle n} {\displaystyle n} is the Coxeter group of Type B n {\displaystyle B_{n}} {\displaystyle B_{n}}.

Given an element π {\displaystyle \pi } {\displaystyle \pi } of the hyperoctahedral group of order n {\displaystyle n} {\displaystyle n} a Type B descent of π {\displaystyle \pi } {\displaystyle \pi } is an index i ∈ { 0 , 1 , … , n − 1 } {\displaystyle i\in \{0,1,\ldots ,n-1\}} {\displaystyle i\in \{0,1,\ldots ,n-1\}} for which π ( i ) > π ( i − 1 ) {\displaystyle \pi (i)>\pi (i-1)} {\displaystyle \pi (i)>\pi (i-1)}, with the convention that π ( 0 ) = 0 {\displaystyle \pi (0)=0} {\displaystyle \pi (0)=0}. The Type B Eulerian number B ( n , k ) {\displaystyle B(n,k)} {\displaystyle B(n,k)} is the number of elements of the hyperoctahedral group of order n {\displaystyle n} {\displaystyle n} with exactly k {\displaystyle k} {\displaystyle k} descents.[10] They are given by the following formula:[11]

B ( n , k ) = ∑ i = 1 k ( − 1 ) k − i ( n k − i ) ( 2 i − 1 ) n − 1 . {\displaystyle B(n,k)=\sum _{i=1}^{k}(-1)^{k-i}{\binom {n}{k-i}}(2i-1)^{n-1}.} {\displaystyle B(n,k)=\sum _{i=1}^{k}(-1)^{k-i}{\binom {n}{k-i}}(2i-1)^{n-1}.}

The table of B ( n , k ) {\displaystyle B(n,k)} {\displaystyle B(n,k)} (sequence A060187 in the OEIS) is

 k
n 
 0 1 2 3 4 5
0 1
1 11
2 161
3 123231
4 176230761
5 1237168216822371

The corresponding polynomials M n ( x ) = ∑ k = 0 n B ( n , k ) x k {\displaystyle M_{n}(x)=\sum _{k=0}^{n}B(n,k)x^{k}} {\displaystyle 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.[12]

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 ≥ 1 {\displaystyle n\geq 1} {\displaystyle n\geq 1},

∑ i = 0 ∞ ( 2 i + 1 ) n x i = M n ( x ) ( 1 − x ) n + 1 . {\displaystyle \sum _{i=0}^{\infty }(2i+1)^{n}x^{i}={\frac {M_{n}(x)}{(1-x)^{n+1}}}.} {\displaystyle \sum _{i=0}^{\infty }(2i+1)^{n}x^{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.[13]

Eulerian numbers of the second order

The permutations of the multiset { 1 , 1 , 2 , 2 , … , n , n } {\textstyle \{1,1,2,2,\ldots ,n,n\}} {\textstyle \{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 ( 2 n − 1 ) ! ! {\textstyle (2n-1)!!} {\textstyle (2n-1)!!}. These are called Stirling permutations.

The Eulerian number of the second order, denoted ⟨ ⟨ n m ⟩ ⟩ {\textstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle } {\textstyle \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:

⟨ ⟨ n k ⟩ ⟩ = ( 2 n − k − 1 ) ⟨ ⟨ n − 1 k − 1 ⟩ ⟩ + ( k + 1 ) ⟨ ⟨ n − 1 k ⟩ ⟩ , {\displaystyle \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 ,} {\displaystyle \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:

⟨ ⟨ 0 k ⟩ ⟩ = [ k = 0 ] . {\displaystyle \left\langle \!\!\left\langle {0 \atop k}\right\rangle \!\!\right\rangle =[k=0].} {\displaystyle \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 ) := ∑ k = 0 n ⟨ ⟨ n k ⟩ ⟩ x k {\displaystyle P_{n}(x):=\sum _{k=0}^{n}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle x^{k}} {\displaystyle 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 ) = ( 2 n x + 1 ) P n ( x ) − x ( x − 1 ) P n ′ ( x ) {\displaystyle P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)} {\displaystyle P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)}

with initial condition P 0 ( x ) = 1 {\displaystyle P_{0}(x)=1} {\displaystyle P_{0}(x)=1}. The latter recurrence may be written in a somewhat more compact form by means of an integrating factor:

( x − 1 ) − 2 n − 2 P n + 1 ( x ) = ( x ( 1 − x ) − 2 n − 1 P n ( x ) ) ′ {\displaystyle (x-1)^{-2n-2}P_{n+1}(x)=\left(x\,(1-x)^{-2n-1}P_{n}(x)\right)^{\prime }} {\displaystyle (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 ) − 2 n P n ( x ) {\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)} {\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}

satisfies a simple autonomous recurrence:

u n + 1 = ( x 1 − x u n ) ′ , u 0 = 1 {\displaystyle u_{n+1}=\left({\frac {x}{1-x}}u_{n}\right)^{\prime },\quad u_{0}=1} {\displaystyle 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 ) 2 n u n ( x ) {\textstyle P_{n}(x)=(1-x)^{2n}u_{n}(x)} {\textstyle 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

∑ i = 1 ∞ i n x i = x A n ( x ) ( 1 − x ) n + 1 {\displaystyle \sum _{i=1}^{\infty }i^{n}x^{i}={\frac {xA_{n}(x)}{(1-x)^{n+1}}}} {\displaystyle \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,[14] they satisfy the identity

∑ m = 0 ∞ { n + m m } x m = x P n ( x ) ( 1 − x ) 2 n + 1 {\displaystyle \sum _{m=0}^{\infty }\left\{{n+m \atop m}\right\}x^{m}={\frac {xP_{n}(x)}{(1-x)^{2n+1}}}} {\displaystyle \sum _{m=0}^{\infty }\left\{{n+m \atop m}\right\}x^{m}={\frac {xP_{n}(x)}{(1-x)^{2n+1}}}}

where again the { n k } {\displaystyle \left\{{n \atop k}\right\}} {\displaystyle \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:

 k
n 
 0 1 2 3 4 5 6 7 8
0 1
1 1
2 12
3 186
4 1225824
5 152328444120
6 1114145244003708720
7 124056103212058140339845040
8 14941995019580064402078530434113640320
9 11004672601062500576550012440064110262963733920362880

The sum of the n-th row, which is also the value P n ( 1 ) {\textstyle P_{n}(1)} {\textstyle P_{n}(1)}, is ( 2 n − 1 ) ! ! {\textstyle (2n-1)!!} {\textstyle (2n-1)!!}.

Indexing the second-order Eulerian numbers comes in three flavors:

  • (sequence A008517 in the OEIS) following Riordan and Comtet,
  • (sequence A201637 in the OEIS) following Graham, Knuth, and Patashnik,
  • (sequence A340556 in the OEIS), extending the definition of Gessel and Stanley.

References

Citations

  1. Euler, Leonhard (1755-01-01). "Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum, volume 1". Academiae Imperialis Scientiarum Petropolitanae: 1–880.
  2. Euler, Leonhard; Aycock, Alexander (2019-05-24), Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum, arXiv, doi:10.48550/arXiv.1905.10438, arXiv:1905.10438, retrieved 2026-04-21
  3. Comtet (1974), p. 243.
  4. Comtet (1974), p. 51.
  5. Graham, Knuth & Patashnik (1994), Exercise 6.65.
  6. Worpitzky, J. (1883). "Studien über die Bernoullischen und Eulerschen Zahlen". Journal für die reine und angewandte Mathematik. 94: 203–232.
  7. Petersen (2015), p. 14.
  8. Knuth, Donald Ervin (1997). The art of computer programming (3rd ed.). Reading, Mass: Addison-Wesley. p. 36. ISBN 978-0-201-89683-1.
  9. Qi, Feng; Guo, Bai-Ni (2017-08-01). "Explicit formulas and recurrence relations for higher order Eulerian polynomials". Indagationes Mathematicae. 28 (4): 884–891. doi:10.1016/j.indag.2017.06.010. ISSN 0019-3577.
  10. Chow, Chak-On; Gessel, Ira M. (March 2007). "On the descent numbers and major indices for the hyperoctahedral group". Advances in Applied Mathematics. 38 (3): 275–301. doi:10.1016/j.aam.2006.07.003.
  11. Sloane, N. J. A. (ed.). "Sequence A060187 (Triangle read by rows: Eulerian numbers of type B)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  12. Schoenberg, I. J. (1972). "Cardinal Interpolation and Spline Functions IV. The Exponential Euler Splines". Linear Operators and Approximation / Lineare Operatoren und Approximation: 382–404. doi:10.1007/978-3-0348-7283-6_34. ISBN 978-3-0348-7285-0.
  13. Petersen (2015), Part III.
  14. Gessel, Ira; Stanley, Richard P (1 January 1978). "Stirling polynomials". Journal of Combinatorial Theory, Series A. 24 (1): 24–33. doi:10.1016/0097-3165(78)90042-0.