Dobinski's Formula

Gives the $n$th Bell Number,

$$B_n={1\over e}\sum_{k=0}^\infty {k^n\over k!}.$$ (1)

It can be derived by dividing the formula for a Stirling Number of the Second Kind by $m!$, yielding

$${m^n\over m!}=\sum_{k=1}^m \left\{\matrix{n\cr k\cr}\right\} {1\over(m-k)!}.$$ (2)

Then

$$\sum_{m=1}^\infty {m^n\over m!}\lambda^m=\left({\sum_{k=1}^n... ...\right) \left({\sum_{k=0}^\infty {\lambda^j\over j!}}\right),$$ (3)

and

$$\sum_{k=1}^n\left\{\matrix{n\cr k\cr}\right\}\lambda^k = e^{-\lambda}\sum_{m=1}^\infty {m^n\over m!} \lambda^m.$$ (4)

Now setting $\lambda=1$ gives the identity (Dobinski 1877; Rota 1964; Berge 1971, p. 44; Comtet 1974, p. 211; Roman 1984, p. 66; Lupas 1988; Wilf 1990, p. 106; Chen and Yeh 1994; Pitman 1997).

References

Berge, C. Principles of Combinatorics. New York: Academic Press, 1971.

Chen, B. and Yeh, Y.-N. ``Some Explanations of Dobinski's Formula.'' Studies Appl. Math. 92, 191-199, 1994.

Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Boston, MA: Reidel, 1974.

Dobinski, G. ``Summierung der Reihe $\sum n^m/n!$ für $m=1$, 2, 3, 4, 5, ....'' Grunert Archiv (Arch. Math. Phys.) 61, 333-336, 1877.

Foata, D. La série génératrice exponentielle dans les problèmes d'énumération. Vol. 54 of Séminaire de Mathématiques supérieures. Montréal, Canada: Presses de l'Université de Montréal, 1974.

Lupas, A. ``Dobinski-Type Formula for Binomial Polynomials.'' Stud. Univ. Babes-Bolyai Math. 33, 30-44, 1988.

Pitman, J. ``Some Probabilistic Aspects of Set Partitions.'' Amer. Math. Monthly 104, 201-209, 1997.

Roman, S. The Umbral Calculus. New York: Academic Press, 1984.

Rota, G.-C. ``The Number of Partitions of a Set.'' Amer. Math. Monthly 71, 498-504, 1964.

Wilf, H. Generatingfunctionology, 2nd ed. San Diego, CA: Academic Press, 1990.