1. ## Bell numbers

The nth Bell number $\displaystyle B_n$ is the number of partitions of a set having $\displaystyle n$ elements. The sequence begins $\displaystyle 1,1,2,5,15,52...$.

Show that the exponential generating function of the Bell numbers is

$\displaystyle G(z)=\sum_{n=0}^\infty B_n\frac{z^n}{n!} = e^{e^z-1}$

2. Lemma: Let $\displaystyle a_n(k)$ 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 $\displaystyle \sum_{n=0}^{\infty}{\tfrac{a_n(k)}{n!}\cdot x^n}=(e^x -1)^{k}$

Proof

Let's compute the coefficient of $\displaystyle x^n$ of the RHS.

Since $\displaystyle e^x - 1 = x + {\textstyle{{x^2 } \over {2!}}} + ...$ it follows that our coefficient is: $\displaystyle \sum\limits_{a_1 + ... + a_k = n} {{\textstyle{1 \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}}$

Now: $\displaystyle \sum\limits_{a_1 + ... + a_k = n} {{\textstyle{{n!} \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}} = \sum\limits_{a_1 + ... + a_k = n} {{\textstyle{{\left( {a_1 + ... + a_k } \right)!} \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}}$ and each term is the number of ordered permutations in which you can have $\displaystyle a_1$ elements in box number 1, ... -permutations with repetition -

So the coefficient is actually $\displaystyle {\textstyle{{a_n \left( k \right)} \over {n!}}}$ $\displaystyle \square$

Next note that $\displaystyle \left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\} = {\textstyle{1 \over {k!}}} \cdot a_n \left( k \right)$ -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: $\displaystyle \sum\limits_{n = 0}^\infty {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\} \cdot {\textstyle{{x^n } \over {n!}}}} = {\textstyle{{\left( {e^x - 1} \right)^k } \over {k!}}}$ and summing over k : $\displaystyle e^{e^x - 1} = \sum\limits_{k \ge 0} {{\textstyle{{\left( {e^x - 1} \right)^k } \over {k!}}}} = \sum\limits_{k \ge 0} {\sum\limits_{n \ge 0} {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\} \cdot {\textstyle{{x^n } \over {n!}}}} } = \sum\limits_{n \ge 0} {\left( {\sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\}} } \right) \cdot {\textstyle{{x^n } \over {n!}}}} \$

Since: $\displaystyle B_n = \sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\}}$ we are done $\displaystyle \square$

3. Very nice!
Here is my proof.

First notice that the Bell numbers are of "binomial type"; i.e. they satisfy the recurrence $\displaystyle B_{n+1}=\sum_{j=0}^n{n \choose j}B_j$. You can see that by induction, considering where to put the $\displaystyle (n+1)^{\mbox{st}}$ object; it can belong to a part by itself (in $\displaystyle B_n$ different ways), or it can belong to a two-object part with $\displaystyle {n \choose 1}$ choices for the other object and $\displaystyle B_{n-1}$ ways to partition the remaining objects, etc.

Now let $\displaystyle G(z)$ be the generating function. Differentiating is equivalent to shifting the sequence one place to the left. Moreover, multiplying by $\displaystyle e^z$ is equivalent to taking the binomial convolution : if $\displaystyle f(z)=\sum_{j=0}^\infty a_j\frac{z^j}{j!}$ then the coefficient of $\displaystyle \frac{z^n}{n!}$ in $\displaystyle e^zf(z)$ is $\displaystyle \sum_{j=0}^n{n \choose j}a_j$.

So we know that the generating function satisfies the differential equation $\displaystyle G'(z)=e^zG(z)$. So $\displaystyle G(z)=e^{e^z+C}$. Since we have $\displaystyle G(0)=1$, we must have $\displaystyle C=-1, \: \: G(z)=e^{e^z-1}$