Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
1  
@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
show 2 more comments

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.