# Math Help - Bell numbers

1. ## Bell numbers

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

Show that the exponential generating function of the Bell numbers is

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

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

Proof

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

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

Now: $
\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 $a_1$ elements in box number 1, ... -permutations with repetition -

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

Next note that $
\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: $
\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 : $
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: $
B_n = \sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c}
n \\
k \\
\end{array}} \right\}}
$
we are done $\square$

3. Very nice!
Here is my proof.

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

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

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