A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://en.wikipedia.org/wiki/Eulerian_number below:

Eulerian number - Wikipedia

Polynomial sequence

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

Leonhard Euler investigated them and associated polynomials in his 1755 book Institutiones calculi differentialis.

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 A ( n , k ) {\textstyle A(n,k)} are E ( n , k ) {\textstyle E(n,k)} and ⟨ n k ⟩ {\displaystyle \textstyle \left\langle {n \atop k}\right\rangle } .

The Eulerian polynomials 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}.}

The Eulerian numbers 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}.}

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

A plot of the Eulerian numbers with the second argument fixed to 5. 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}.}

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)} (sequence A008292 in the OEIS) for 0 ≤ n ≤ 9 {\textstyle 0\leq n\leq 9} are:

 k

n 

0 1 2 3 4 5 6 7 8 0 1 1 1 2 1 1 3 1 4 1 4 1 11 11 1 5 1 26 66 26 1 6 1 57 302 302 57 1 7 1 120 1191 2416 1191 120 1 8 1 247 4293 15619 15619 4293 247 1 9 1 502 14608 88234 156190 88234 14608 502 1

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

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} and k {\textstyle k} , the values of 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.}

Likewise, the Eulerian polynomials can be computed by the recurrence

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.}

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.}

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 {\displaystyle n} elements, so their sum equals the factorial n ! {\displaystyle n!} . I.e.

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

as well as A ( 0 , 0 ) = 0 ! {\displaystyle A(0,0)=0!} . To avoid conflict with the empty sum convention, it is convenient to simply state the theorems for n > 0 {\displaystyle n>0} only.

Much more generally, for a fixed function f : R → C {\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {C} } integrable on the interval ( 0 , n ) {\displaystyle (0,n)} [3]

∑ 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){\mathrm {d} }x_{1}\cdots {\mathrm {d} }x_{n}}

Worpitzky's identity[4] expresses 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}.}

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}}.}

They appear as the coefficients of the polylogarithm. Li − n ⁡ ( z ) = 1 ( 1 − z ) n + 1 ∑ k = 0 n − 1 ⟨ 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}\left\langle {n \atop k}\right\rangle z^{n-k}\qquad (n=1,2,3,\ldots ),}

Formulas involving alternating sums[edit]

The alternating sum of the Eulerian numbers for a fixed value of n {\textstyle n} is related to the Bernoulli number 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.}

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}

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}
Formulas involving the polynomials[edit]

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})}

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)}

An explicit expression for Eulerian polynomials is[5]

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}}

where { n k } {\textstyle \left\{{n \atop k}\right\}} is the Stirling number of the second kind.

Geometric interpretations[edit]

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}}

implies that the Eulerian numbers form the h ∗ {\displaystyle h^{\ast }} -vector of the standard n {\displaystyle n} -dimensional hypercube, which is the convex hull of all 0 , 1 {\displaystyle 0,1} -vectors in 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}} means that the Eulerian numbers also form the h {\displaystyle h} -vector of the simple polytope which is dual to the n {\displaystyle n} -dimensional permutohedron, which is the convex hull of all permutations of the vector ( 1 , 2 , … , n ) {\displaystyle (1,2,\ldots ,n)} in R n {\displaystyle \mathbb {R} ^{n}} .

In fact, as explained by Richard Stanley in an answer to a MathOverflow question, these two geometric guises of the Eulerian numbers are closely linked.

Type B Eulerian numbers[edit]

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

Given an element π {\displaystyle \pi } of the hyperoctahedral group of order n {\displaystyle n} a Type B descent of π {\displaystyle \pi } is an index i ∈ { 0 , 1 , … , n − 1 } {\displaystyle i\in \{0,1,\ldots ,n-1\}} for which π ( i ) > π ( i − 1 ) {\displaystyle \pi (i)>\pi (i-1)} , with the convention that π ( 0 ) = 0 {\displaystyle \pi (0)=0} . The Type B Eulerian number B ( n , k ) {\displaystyle B(n,k)} is the number of elements of the hyperoctahedral group of order n {\displaystyle n} with exactly k {\displaystyle k} descents; see Chow and Gessel[6].

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

 k

n 

0 1 2 3 4 5 0 1 1 1 1 2 1 6 1 3 1 23 23 1 4 1 76 230 76 1 5 1 237 1682 1682 237 1

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}} are called midpoint Eulerian polynomials because of their use in interpolation and spline theory; see Schoenberg[7].

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} ,

∑ 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}}}.}

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[edit]

The permutations of the multiset { 1 , 1 , 2 , 2 , … , 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)!!} . 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 } , 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 ,}

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].}

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}}

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)}

with initial condition 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 }}

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)}

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}

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)} , 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}}}}

satisfied by the usual Eulerian polynomials. Specifically, as proved by Gessel and Stanley[8], 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}}}}

where again the { n k } {\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 1 2 3 1 8 6 4 1 22 58 24 5 1 52 328 444 120 6 1 114 1452 4400 3708 720 7 1 240 5610 32120 58140 33984 5040 8 1 494 19950 195800 644020 785304 341136 40320 9 1 1004 67260 1062500 5765500 12440064 11026296 3733920 362880

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

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

  1. ^ (L. Comtet 1974, p. 243)
  2. ^ Comtet, Louis. Advanced Combinatorics (PDF). p. 51.
  3. ^ Exercise 6.65 in Concrete Mathematics by Graham, Knuth and Patashnik.
  4. ^ Worpitzky, J. (1883). "Studien über die Bernoullischen und Eulerschen Zahlen". Journal für die reine und angewandte Mathematik. 94: 203–232.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4