Dobinski's formula

In combinatorial mathematics, Dobinski’s formula^[1] states that the number of partitions of a set of n members is

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

This number has come to be called the nth Bell number B_n, after Eric Temple Bell.

The above formula can be seen as a particular case, for x = 0, of the more general relation:

${1 \over e}\sum_{k=x}^\infty {k^n \over (k-x)!} = \sum_{k=0}^n {n \choose k} B_{k} x^{n-k}$

Probabilistic content

Those familiar with probability theory will recognize the expression given by Dobinski's formula as the nth moment of the Poisson distribution with expected value 1. Today, Dobinski's formula is sometimes stated by saying the number of partitions of a set of size n equals the nth moment of that distribution.

A proof

The proof given here is an adaptation to probabilistic language, of the proof given by Rota.^[2]

Combinatorialists use the Pochhammer symbol (x)_n to denote the falling factorial

$(x)_n = x(x-1)(x-2)\cdots(x-n+1)\,$

(whereas, in the theory of special functions, the same notation denotes the rising factorial). If x and n are nonnegative integers, 0 ≤ n ≤ x, then (x)_n is the number of one-to-one functions that map a size-n set into a size-x set.

Let ƒ be any function from a size-n set A into a size-x set B. For any u ∈ B, let ƒ ⁻¹(u) = {v ∈ A : ƒ(v) = u}. Then {ƒ ⁻¹(u) : u ∈ B} is a partition of A, coming from the equivalence relation of "being in the same fiber". This equivalence relation is called the "kernel" of the function ƒ. Any function from A into B factors into

• one function that maps a member of A to that part of the kernel to which it belongs, and
• another function, which is necessarily one-to-one, that maps the kernel into B.

The first of these two factors is completely determined by the partition π that is the kernel. The number of one-to-one functions from π into B is (x)_|π|, where |π| is the number of parts in the partition π. Thus the total number of functions from a size-n set A into a size-x set B is

$\sum_\pi (x)_{|\pi|},\,$

the index π running through the set of all partitions of A. On the other hand, the number of functions from A into B is clearly xⁿ. Therefore we have

$x^n = \sum_\pi (x)_{|\pi|}.\,$

If X is a Poisson-distributed random variable with expected value 1, then we get that the nth moment of this probability distribution is

$E(X^n) = \sum_\pi E((X)_{|\pi|}).\,$

But all of the factorial moments E((X)_k) of this probability distribution are equal to 1. Therefore

$E(X^n) = \sum_\pi 1,\,$

and this is just the number of partitions of the set A. Q.E.D.

Notes and references

1. ^ G. Dobiński, "Summirung der Reihe $\textstyle\sum\frac{n^m}{n!}$ für m = 1, 2, 3, 4, 5, …", Grunert's Archiv, volume 61, 1877, pages 333–336 (Internet Archive: [1]).
2. ^ * Gian-Carlo Rota, "The Number of Partitions of a Set", American Mathematical Monthly, volume 71, number 5, May 1964, pages 498–504.