2
$\begingroup$

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!

  • 1
    @muffel: consider http://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)$.2011-05-15

1 Answers 1

1

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$.

  • 0
    @quanta really great, thanks a lot!2011-05-15