<s>[INST] 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}$?
Thank you in advance!
 [/INST] 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$.
</s>