Eulerian number

Last updated March 07, 2024

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

Definition

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

The Eulerian numbers $A(n,k)$ may 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 ${\textstyle A(n,k)}$ is^[1]

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

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

Basic properties

For fixed ${\textstyle n}$ there is a single permutation which has 0 ascents: ${\textstyle (n,n-1,n-2,\ldots ,1)}$ . Indeed, as ${\tbinom {n}{0}}=1$ for all $n$ , ${\textstyle A(n,0)=1}$ . This formally includes the empty collection of numbers, ${\textstyle n=0}$ . And so ${\textstyle A_{0}(t)=A_{1}(t)=1}$ .
For ${\textstyle k=1}$ the explicit formula implies ${\textstyle A(n,1)=2^{n}-(n+1)}$ , a sequence in $n$ that reads ${\textstyle 0,0,1,4,11,26,57,\dots }$ .
Fully reversing a permutation with ${\textstyle k}$ ascents creates another permutation in which there are ${\textstyle n-k-1}$ ascents. Therefore ${\textstyle A(n,k)=A(n,n-k-1)}$ . So there is also a single permutation which has ${\textstyle n-1}$ ascents, namely the rising permutation ${\textstyle (1,2,\ldots ,n)}$ . So also ${\textstyle A(n,n-1)}$ equals $1$ .
A lavish upper bound is ${\textstyle A(n,k)\leq (k+1)^{n}\cdot (n+2)^{k}}$ . Between the bounds just discussed, the value exceeds $1$ .
For ${\textstyle k\geq n>0}$ , the values are formally zero, meaning many sums over ${\textstyle k}$ can be written with an upper index only up to ${\textstyle n-1}$ . It also means that the polynomials $A_{n}(t)$ are really of degree ${\textstyle n-1}$ for ${\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 ${\textstyle A(n,k)}$ (sequence A008292 in the OEIS ) for ${\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

Computation

For larger values of ${\textstyle n}$ , ${\textstyle 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 ${\textstyle n}$ and ${\textstyle k}$ , the values of ${\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
2	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\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!$ . I.e.

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

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

Much more generally, for a fixed function $f\colon \mathbb {R} \rightarrow \mathbb {C}$ integrable on the interval $(0,n)$ ^[2]

\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^[3] expresses ${\textstyle 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 it, it follows that

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

Formulas involving alternating sums

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

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

Where ${\textstyle \left\{{n \atop k}\right\}}$ is the Stirling numbers of the second kind.

Eulerian numbers of the second order

The permutations of the multiset ${\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 ${\textstyle (2n-1)!!}$ . The Eulerian number of the second order, denoted $\scriptstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle$ , 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:

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 P_n (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 P_n(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 ${\textstyle P_{n}(x)=(1-x)^{2n}u_{n}(x)}$ , and the Eulerian numbers of second order as their coefficients.

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 ${\textstyle P_{n}(1)}$ , is ${\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.

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

<span class="mw-page-title-main">Quantum harmonic oscillator</span> Important, well-understood quantum mechanical model

The quantum harmonic oscillator is the quantum-mechanical analog of the classical harmonic oscillator. Because an arbitrary smooth potential can usually be approximated as a harmonic potential at the vicinity of a stable equilibrium point, it is one of the most important model systems in quantum mechanics. Furthermore, it is one of the few quantum-mechanical systems for which an exact, analytical solution is known.

In mathematics, the (signed and unsigned) Lah numbers are coefficients expressing rising factorials in terms of falling factorials and vice versa. They were discovered by Ivo Lah in 1954. Explicitly, the unsigned Lah numbers $are given by the formula involving the binomial coefficient$

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.

In mathematics, the Hermite polynomials are a classical orthogonal polynomial sequence.

In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the immanant.

In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Catalan.

In mathematics, the falling factorial is defined as the polynomial

The Touchard polynomials, studied by Jacques Touchard, also called the exponential polynomials or Bell polynomials, comprise a polynomial sequence of binomial type defined by

The Basel problem is a problem in mathematical analysis with relevance to number theory, concerning an infinite sum of inverse squares. It was first posed by Pietro Mengoli in 1650 and solved by Leonhard Euler in 1734, and read on 5 December 1735 in The Saint Petersburg Academy of Sciences. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate fame when he was twenty-eight. Euler generalised the problem considerably, and his ideas were taken up more than a century later by Bernhard Riemann in his seminal 1859 paper "On the Number of Primes Less Than a Given Magnitude", in which he defined his zeta function and proved its basic properties. The problem is named after Basel, hometown of Euler as well as of the Bernoulli family who unsuccessfully attacked the problem.

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by $or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.$

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles.

In mathematics, the secondary measure associated with a measure of positive density ρ when there is one, is a measure of positive density μ, turning the secondary polynomials associated with the orthogonal polynomials for ρ into an orthogonal system.

In mathematics, the Dickson polynomials, denoted $D n (x, α)$ , form a polynomial sequence introduced by L. E. Dickson (1897). They were rediscovered by Brewer (1961) in his study of Brewer sums and have at times, although rarely, been referred to as Brewer polynomials.

In machine learning, the radial basis function kernel, or RBF kernel, is a popular kernel function used in various kernelized learning algorithms. In particular, it is commonly used in support vector machine classification.

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

References

Eulerus, Leonardus [Leonhard Euler] (1755). Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Foundations of differential calculus, with applications to finite analysis and series]. Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
Carlitz, L. (1959). "Eulerian Numbers and polynomials". Math. Mag. 32 (5): 247–260. doi:10.2307/3029225. JSTOR 3029225.
Gould, H. W. (1978). "Evaluation of sums of convolved powers using Stirling and Eulerian Numbers". Fib. Quart. 16 (6): 488–497.
Desarmenien, Jacques; Foata, Dominique (1992). "The signed Eulerian numbers". Discrete Math. 99 (1–3): 49–58. doi: 10.1016/0012-365X(92)90364-L .
Lesieur, Leonce; Nicolas, Jean-Louis (1992). "On the Eulerian Numbers M=max (A(n,k))". Europ. J. Combinat. 13 (5): 379–399. doi: 10.1016/S0195-6698(05)80018-6 .
Butzer, P. L.; Hauss, M. (1993). "Eulerian numbers with fractional order parameters". Aequationes Mathematicae . 46 (1–2): 119–142. doi:10.1007/bf01834003. S2CID 121868847.
Koutras, M.V. (1994). "Eulerian numbers associated with sequences of polynomials". Fib. Quart. 32 (1): 44.
Graham; Knuth; Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley. pp. 267–272.
Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (1999). "On certain summation problems and generalizations of Eulerian polynomials and numbers". Discrete Math. 204 (1–3): 237–247. doi: 10.1016/S0012-365X(98)00379-3 .
Boyadzhiev, Khristo N. (2007). "Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials". arXiv: 0710.1124 [math.CA].
Petersen, T. Kyle (2015). "Eulerian numbers". Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. pp. 3–18. doi:10.1007/978-1-4939-3091-3_1. ISBN 978-1-4939-3090-6.

Citations

↑ (L. Comtet 1974, p. 243)
↑ Exercise 6.65 in Concrete Mathematics by Graham, Knuth and Patashnik.
↑ Worpitzky, J. (1883). "Studien über die Bernoullischen und Eulerschen Zahlen". Journal für die reine und angewandte Mathematik. 94: 203–232.
↑ 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.

External links

Eulerian Polynomials at OEIS Wiki.
"Eulerian Numbers". MathPages.com.
Weisstein, Eric W. "Eulerian Number". MathWorld .
Weisstein, Eric W. "Euler's Number Triangle". MathWorld .
Weisstein, Eric W. "Worpitzky's Identity". MathWorld .
Weisstein, Eric W. "Second-Order Eulerian Triangle". MathWorld .
Euler-matrix (generalized rowindexes, divergent summation)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] (L. Comtet 1974, p. 243)

[2] Exercise 6.65 in Concrete Mathematics by Graham, Knuth and Patashnik.

[3] Worpitzky, J. (1883). "Studien über die Bernoullischen und Eulerschen Zahlen". Journal für die reine und angewandte Mathematik. 94: 203–232.

[4] 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.

[1]

[2]

[3]

[4]