info prev up next book cdrom email home

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

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

Making the definition
$\displaystyle b_{n,1}$ $\textstyle =$ $\displaystyle 1$ (2)
$\displaystyle b_{1,n}$ $\textstyle =$ $\displaystyle 1$ (3)

together with the Recurrence Relation
\begin{displaymath}
b_{n,k}=n b_{n,k-1}+k b_{n-1,k}
\end{displaymath} (4)

for $n>k$ then gives
\begin{displaymath}
\left\langle{n\atop k}\right\rangle{}=b_{k,n-k+1}.
\end{displaymath} (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

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

Eulerian numbers also arise in the surprising context of integrating the Sinc Function, and also in sums of the form
\begin{displaymath}
\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},
\end{displaymath} (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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25