Eulerian Number

The number of Permutations of length $n$ with $k\leq n$ Runs, denoted $\left\langle{n\atop k}\right\rangle{}$, $A_{n,k}$, or $A(n,k)$. The Eulerian numbers are given explicitly by the sum

$$\left\langle{n\atop k}\right\rangle{}=\sum_{j=0}^k (-1)^j{n+1\choose j}(k-j)^n.$$ (1)

Making the definition

$$b_{n,1} = 1$$ (2)

$$b_{1,n} = 1$$ (3)

together with the Recurrence Relation

$$b_{n,k}=n b_{n,k-1}+k b_{n-1,k}$$ (4)

for $n>k$ then gives

$$\left\langle{n\atop k}\right\rangle{}=b_{k,n-k+1}.$$ (5)

The arrangement of the numbers into a triangle gives Euler's Triangle, whose entries are 1, 1, 1, 1, 4, 1, 1, 11, 11, 1, ... (Sloane's A008292). Therefore, they 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.

The Eulerian numbers satisfy

$$\sum_{k=1}^n \left\langle{n\atop k}\right\rangle{}=n!.$$ (6)

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^n r^k=\mathop{\rm Li}\nolimits _{-n}(r) ... ...}} \sum_{i=1}^n \left\langle{n\atop i}\right\rangle{} r^{n-i},$$ (7)

where $\mathop{\rm Li}\nolimits _m(z)$ is the Polylogarithm function.

See also Combination Lock, Euler Number, Euler's Triangle, Euler Zigzag Number, Polylogarithm, Sinc Function, Worpitzky's Identity, Z-Transform

References

Carlitz, L. ``Eulerian Numbers and Polynomials.'' Math. Mag. 32, 247-260, 1959.

Foata, D. and Schützenberger, M.-P. Théorie Géométrique des Polynômes Eulériens. Berlin: Springer-Verlag, 1970.

Kimber, A. C. ``Eulerian Numbers.'' Supplement to Encyclopedia of Statistical Sciences. (Eds. S. Kotz, N. L. Johnson, and C. B. Read). New York: Wiley, pp. 59-60, 1989.

Salama, I. A. and Kupper, L. L. ``A Geometric Interpretation for the Eulerian Numbers.'' Amer. Math. Monthly 93, 51-52, 1986.

Sloane, N. J. A. Sequence A008292 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.