The nth Bell number is the number of partitions of a set having elements. The sequence begins .
Show that the exponential generating function of the Bell numbers is
Lemma: Let be the number of ordered partitions of a set of n elements in k sets. - or the number of ways in which you can distribute n balls into k boxes -
Then
Proof
Let's compute the coefficient of of the RHS.
Since it follows that our coefficient is:
Now: and each term is the number of ordered permutations in which you can have elements in box number 1, ... -permutations with repetition -
So the coefficient is actually
Next note that -the LHS is the stirling number of the second kind, or, the number of partitions of a set of n elements into k sets (here we do not care about the order) -
Hence: and summing over k :
Since: we are done
Very nice!
Here is my proof.
First notice that the Bell numbers are of "binomial type"; i.e. they satisfy the recurrence . You can see that by induction, considering where to put the object; it can belong to a part by itself (in different ways), or it can belong to a two-object part with choices for the other object and ways to partition the remaining objects, etc.
Now let be the generating function. Differentiating is equivalent to shifting the sequence one place to the left. Moreover, multiplying by is equivalent to taking the binomial convolution : if then the coefficient of in is .
So we know that the generating function satisfies the differential equation . So . Since we have , we must have