Bell Numbers and Equating Coefficients

I need help solving the following exercise:

Let B(n) be the Bell - Numbers of $[n]$ and $$\exp(x) := \sum_{n\geq 0} \frac{x^n}{n!}$$ the exponential function.

Prove by equating the coefficients and using $$B(n) = \sum\limits_{a_1+\cdots+a_k=n, a_i \geq 1} \frac{1}{k!} \binom{n}{a_1 \cdots a_k}$$ that for $n \geq 0$ $$\sum\limits_{n \geq 0} B(n)/n! \cdot x^n = \exp(\exp(x) - 1)$$

I tried to play around with the equation but haven't gotten anywhere yet.

For the left side I am not sure how to handle the range of the 2nd sum:

$$\sum\limits_{n \geq 0} B(n)/n!\cdot x^n = \sum\limits_{n \geq 0} \frac{\sum\limits_{a_1+\cdots+a_k=n, a_i \geq 1}\frac{1}{k!}\binom n {a_1 \cdots a_k}}{n!}\cdot x^n$$

How do I get this simplified and converted to a polynomial form?

I know that $$\exp(x) = \sum_{n=0}^\infty \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$$ But how do I proceed for $\exp(\exp(x)-1) = e^{e^x-1}$?

-
We can see that, $$exp(exp(x)-1) = \sum_{n=0}^{\infty}{\frac{(exp(x)-1)^n}{n!}} = \sum_{n=0}^{\infty}{\frac{\left[ { \left( \sum_{m=0}^{\infty}{\frac{x^m}{m!}} \right)}-1 \right]^n}{n!}}$$ – Nicolas Villanueva May 15 '11 at 18:12
May be useful to include what $\binom{n}{a_1 \cdots a_k}$ is. – quanta May 15 '11 at 18:18
It's a multinomial... where $a_1+\ldots + a_k = n$, so essentially the $a_i$'s partition n. – Nicolas Villanueva May 15 '11 at 18:24
Is it ${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}$. This does not match up with what I found. – quanta May 15 '11 at 18:24
@muffel: consider en.wikipedia.org/wiki/Dobinski's_formula, and note that $\exp(e^x-1)$ is the moment generating function of the Poisson(1) distribution, whose moments are given by ${\rm E}(X^n)=B(n)$. – Shai Covo May 15 '11 at 18:42

We are interested in expansion of the term $\exp(\exp(x)-1)$, now $$\exp(x) - 1 = \sum_{n=1}^\infty \frac{x^n}{n!}$$ and since $\displaystyle \exp(z) = \sum_{m=0}^\infty \frac{z^m}{m!}$ we should start by considering $\displaystyle \left(\sum_{n=1}^\infty \frac{x^n}{n!}\right)^m$ for $m=2,3,\ldots$, here is a table just for $m=2$, extrapolation will give all other $m$:

$$\begin{array}{c|l} \sum_{n=1}^\infty \frac{x^n}{n!} & \frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\ldots \\ \times \frac{x^1}{1!} & \frac{x^2}{1!1!}+\frac{x^3}{1!2!}+\frac{x^4}{1!3!}+\frac{x^5}{1!4!}+\frac{x^6}{1!5!}+\ldots \\ \times \frac{x^2}{2!} & \frac{x^3}{1!2!}+\frac{x^4}{2!2!}+\frac{x^5}{2!3!}+\frac{x^6}{2!4!}+\frac{x^7}{2!5!}+\ldots \\ \times \frac{x^3}{3!} & \frac{x^4}{1!3!}+\frac{x^5}{2!3!}+\frac{x^6}{3!3!}+\frac{x^7}{3!4!}+\frac{x^8}{3!5!}+\ldots \\ \vdots & \cdots \end{array}$$

and so we find $$\exp\left(\sum_{n=1}^\infty \frac{x^n}{n!}\right) = \frac{1}{0!} + \sum_{n=1}^\infty \left(\frac{1}{1!} \sum_{a=n}\frac{x^{a}}{a!} + \frac{1}{2!} \sum_{a+b=n}\frac{x^{a+b}}{a!b!} + \frac{1}{3!} \sum_{a+b+c=n}\frac{x^{a+b+c}}{a!b!c!} + \ldots \right)$$

So you can try to see whether this is equal to the strange multinomial coefficient you have written.

Now I will show how to use the above formula to compute Bell numbers,

First the 0th Bell number (coefficient of $x^0$) is just 1/0! = 1. The first Bell number is the coefficient of $x^1$, and the only term which contributes this is 1/1! x^1/1! so B_1 = 1 as well. A more interesting one is B_3:

All contributions to $x^3$ terms come from $\sum_{n=1}^\infty \frac{1}{1!} \sum_{a=n}\frac{x^{a}}{a!} + \frac{1}{2!} \sum_{a+b=n}\frac{x^{a+b}}{a!b!} + \frac{1}{3!} \sum_{a+b+c=n}\frac{x^{a+b+c}}{a!b!c!}$ we could remove the "..." part since a+b+c+d+.. can never be 3 (since all the numbers must be $\ge 1$).

Now consider each sum one at a time,

• {a = 3}
• {a = 2,b = 1}, {a = 1, b = 2}
• {a = 1,b = 1,c = 1}

so we have the $x^3$ coefficient being: $1/1! x^3/3! + 1/2! (x^3/1!2! + x^3/2!1!) + 1/3! x^3/1!1!1! = 5/6 x^3$ so the third bell number is $5$.

-
There needs to be an index shift - either for the left or the right side. Which one would you propose? Additionally I don't find the $x^n$ on your part. – muffel May 15 '11 at 18:33
@muffel, where? – quanta May 15 '11 at 18:36
@muffel He shifted for the exp($x$)-1 term already. And to get $x^n$ you need to fix an $n$ on both sides. – Nicolas Villanueva May 15 '11 at 18:41
@Nicolas Villanueva It's $\sum\limits_{n\geq 0} \cdots$ on the left, and $\sum\limits_{n\geq 1}$ on the right, isn't it? What do you mean by "fix an n on both sides"? The $x^n$ is given on the left side but missing on the right one. How can this be fixed? – muffel May 15 '11 at 18:54
@muffel, what is? – quanta May 15 '11 at 18:55