# Prove for Bell numbers

I need to prove the following formula for Bell numbers:

$$B(n) = \sum_{a_1 + \cdots + a_k = n, a_i \geq 1} \frac{1}{k!} \binom{n}{a_1 \cdots a_k}$$

Do you have any hint for me for getting this done?

-
This is an immediate consequence of the definitions of the Bell numbers and the multinomial coefficient. – Phira May 14 '11 at 11:36
We defined the Bell numbers quite short as "B(0) := 1, B(n) for n $\geq$ 1 := the quantity of set partitions of $[n]$". $[n]$ is defined as $\{1,\cdots,n\}$. How do I combine that defintion and the one of the multinomial coefficient with the given formula? – muffel May 14 '11 at 11:44
I am struggling with this sum. Do you have a definition for $\sum_{a_1+...+a_k = n, \, a_k \geq 1}$ – monoid May 14 '11 at 13:43
It means "sum over all tuples $(a_1,\dotsc,a_k)$ such that their sum is $n$ and they're all greater or equal to $1$". – joriki May 15 '11 at 17:13

To count the number of partitions of $[n]$, you can go through all the ways of carving $n$ up into bin sizes $a_1,\dotsc,a_k$ that add up to $n$ and then count the number of ways of distributing $n$ objects into those bins, which is the multinomial coefficient. However, this overcounts, since if you swap two bins, you get the same partition, but you get a separate count in the sum. So you have to divide by the number of permutations of the $k$ bins, which is $k!$.
While this is the easiest way to get the factor of $k!$, it's also instructive to look at how different permutations of the bins are (over)counted in the sum. If you swap two bins of the same size, you get another distribution of the elements over the same bin sizes, so this overcounting is in the multinomial coefficient, so to speak. On the other hand, if you swap two bins of different sizes, you get a different arrangement of the same bin sizes, so this overcounting is in the sum, so to speak.
We have $$B(n) = \sum_{k=1}^n {n\brace k}$$ and the bivariate generating function of the Stirling numbers of the second kind is $$G(z, u) = \exp(u(\exp(z)-1)).$$ Substituting this into the sum we get $$B(n) = \sum_{k=1}^n n! [z^n] [u^k] \exp(u(\exp(z)-1)) = \sum_{k=1}^n n! [z^n] \frac{(\exp(z)-1)^k}{k!}.$$ Observe that $$[z^n] \frac{(\exp(z)-1)^k}{k!} = \frac{1}{k!} \sum_{a_1+a_2+\cdots+a_k=n, a_i\ge 1} \frac{1}{\prod_{q=1}^k a_q!}$$ for a final answer of $$\sum_{k=1}^n n! \frac{1}{k!} \sum_{a_1+a_2+\cdots+a_k=n, a_i\ge 1} \frac{1}{\prod_{q=1}^k a_q!}$$ which is $$\sum_{a_1+a_2+\cdots+a_k=n, a_i\ge 1} \frac{1}{k!} {n\choose a_1,a_2,\ldots, a_k}.$$