In combinatorial mathematics, Dobiński’s formula states that the n-th Bell number Bn (i.e., the number of partitions of a set of size n) equals
Contents
The formula is named after G. Dobiński, who published it in 1877.
Probabilistic content
In the probability theory setting, Dobinski's formula represents the nth moment of the Poisson distribution with expected value 1. Sometimes Dobinski's formula is stated as the number of partitions of a set of size n equals the nth moment of that distribution.
Generalization
Dobiński’s formula can be seen as a particular case, for
Proof
The proof given here is an adaptation to probabilistic language of the proof given by Rota.
Combinatorialists use the Pochhammer symbol (x)n to denote the falling factorial
(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 ƒ −1(u) = {v ∈ A : ƒ(v) = u}. Then {ƒ −1(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
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
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 xn. Therefore we have
If X is a Poisson-distributed random variable with expected value 1, then we get that the nth moment of this probability distribution is
But all of the factorial moments E((X)k) of this probability distribution are equal to 1. Therefore
and this is just the number of partitions of the set A. Q.E.D.