TOPICS
Search

Eulerian Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Eulerian number <n; k> gives the number of permutations of {1,2,...,n} having k permutation ascents (Graham et al. 1994, p. 267). Note that a slightly different definition of Eulerian number is used by Comtet (1974), who defines the Eulerian number A(n,k) (sometimes also denoted A_(n,k)) as the number of permutation runs of length k-1, and hence A(n,k)=<n; k-1>.

The Eulerian numbers are given explicitly by the sum

<n; k>=sum_(j=0)^(k+1)(-1)^j(n+1; j)(k-j+1)^n
(1)

(Comtet 1974, p.  243). The Eulerian numbers satisfy the sum identity

sum_(k=0)^n<n; k>=n!
(2)

as well as Worpitzky's identity

sum_(k=1)^n(k+x-1; n)<n; k>=x^n.
(3)

Eulerian numbers also arise in the surprising context of integrating the sinc function, and also in sums of the form

sum_(k=1)^(infty)k^nr^k=Li_(-n)(r)
(4)
=1/((1-r)^(n+1))sum_(i=0)^(n-1)<n; i>r^(n-i),
(5)

where Li_m(z) is the polylogarithm function. <n; k> is therefore given by the coefficient of x^(k+1) in

((1-x)^(n+1)Li_(-n)(x))/x.
(6)

<n; k> has the exponential generating function

sum_(k=0)^inftysum_(n=0)^infty<n; k>(x^n)/(n!)(z^k)/(k!)=((z-1)e^x)/(ze^x-e^(xz)).
(7)

The Eulerian numbers A(n,k) satisfy the recurrence relation

A(n,k)=(n-k+1)A(n-1,k-1)+kA(n-1,k).
(8)

Special cases are given by

<n; 1>=2^n-n-1
(9)
<n; 2>=3^n-2^n(n+1)+1/2n(n+1)
(10)
<n; 3>=4^n-3^n(n+1)+2^(n-1)n(n+1)-1/6(n-1)n(n+1)
(11)

and summarized in the following table.

kOEIS<1; k>, <2; k>, <3; k>, ...
1A0002950, 1, 4, 11, 26, 57, 120, 247, 502, 1013, ...
2A0004600, 0, 1, 11, 66, 302, 1191, 4293, 14608, ...
3A0004980, 0, 0, 1, 26, 302, 2416, 15619, 88234, ...

The arrangement of the numbers A(n,k) into a triangle gives Euler's number triangle

1 1 1 1 4 1 1 11 11 1 1 26 66 26 1 1 57 302 302 57 1 1 120 1191 2416 1191 120 1.
(12)

(OEIS A008292). Therefore, the Eulerian numbers represent a sort of generalization of the binomial coefficients where the defining recurrence relation weights the sum of neighbors by their row and column numbers, respectively.

See also

Combination Lock, Euler Number, Euler's Number Triangle, Euler Prime, Euler Zigzag Number, Permutation Ascent, Permutation Run, Polylogarithm, Simon Newcomb's Problem, Sinc Function, Worpitzky's Identity, Z-Transform

Explore with Wolfram|Alpha

References

Abramson, M. and Moser, W. O. J. "Permutations without Rising or Falling omega-Sequences." Ann. Math. Statist. 38, 1245-1254, 1967.André, D. "Mémoir sur les couples actifs de permutations." Mem. della Pontificia Acad. Romana dei Nuovo Lincei 23, 189-223, 1906.Carlitz, L. "Note on a Paper of Shanks." Amer. Math. Monthly 59, 239-241, 1952.Carlitz, L. "Eulerian Numbers and Polynomials." Math. Mag. 32, 247-260, 1959.Carlitz, L. "Eulerian Numbers and Polynomials of Higher Order." Duke Math. J. 27, 401-423, 1960.Carlitz, L. "A Note on the Eulerian Numbers." Arch. Math. 14, 383-390, 1963.Carlitz, L. and Riordan, J. "Congruences for Eulerian Numbers." Duke Math. J. 20, 339-343, 1953.Carlitz, L.; Roselle, D. P.; and Scoville, R. "Permutations and Sequences with Repetitions by Number of Increase." J. Combin. Th. 1, 350-374, 1966.Cesàro, E. "Dérivées des fonctions de fonctions." Nouv. Ann. 5, 305-327, 1886.Comtet, L. "Permutations by Number of Rises; Eulerian Numbers." §6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 51 and 240-246, 1974.David, F. N.; Kendall, M. G.; and Barton, D. E. Symmetric Function and Allied Tables. Cambridge, England: Cambridge University Press, p. 260, 1966.Dillon, J. F.; Roselle, D. P. "Eulerian Numbers of Higher Order." Duke Math. J. 35, 247-256, 1968.Foata, D. and Schützenberger, M.-P. Théorie géométrique des polynômes Eulériens. Berlin: Springer-Verlag, 1970.Frobenius, F. G. "Ueber die Bernoullischen Zahlen und die Eulerischen Polynome." Sitzungsber. Preuss. Akad. Wiss., pp. 808-847, 1910.Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Eulerian Numbers." §6.2 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 267-272, 1994.Kimber, A. C. "Eulerian Numbers." Supplement to Encyclopedia of Statistical Sciences. (Ed. S. Kotz, N. L. Johnson, and C. B. Read). New York: Wiley, pp. 59-60, 1989.Poussin, F. "Sur une propriété arithmétique de certains polynomes associés aux nombres d'Euler." C. R. Acad. Sci. Paris Sér. A-B 266, A392-A393, 1968.Salama, I. A. and Kupper, L. L. "A Geometric Interpretation for the Eulerian Numbers." Amer. Math. Monthly 93, 51-52, 1986.Schrutka, L. "Eine neue Einleitung der Permutationen." Math. Ann. 118, 246-250, 1941.Shanks, E. B. "Iterated Sums of Powers of the Binomial Coefficients." Amer. Math. Monthly 58, 404-407, 1951.Sloane, N. J. A. Sequences A000295/M3416, A000460/M4795, A000498/M5188, and A008292 in "The On-Line Encyclopedia of Integer Sequences."Tomić, M. "Sur une nouvelle classe de polynômes de la théorie des fonctions spéciales." Publ. Fac. Elect. U. Belgrade, No. 38, 1960.Toscano, L. "Su due sviluppi della potenza di un binomio, q-coefficienti di Eulero." Bull. S. M. Calabrese 16, 1-8, 1965.

Referenced on Wolfram|Alpha

Eulerian Number

Cite this as:

Weisstein, Eric W. "Eulerian Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EulerianNumber.html

Subject classifications