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!

  • 0
    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!}}$$2011-05-15
  • 0
    May be useful to include what $\binom{n}{a_1 \cdots a_k}$ is.2011-05-15
  • 0
    It's a multinomial... where $a_1+\ldots + a_k = n$, so essentially the $a_i$'s partition n.2011-05-15
  • 0
    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.2011-05-15
  • 0
    your definition is correct @quanta2011-05-15
  • 0
    How does this not match up with what you found?2011-05-15
  • 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
    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.2011-05-15
  • 0
    @muffel, where?2011-05-15
  • 0
    @muffel He shifted for the exp($x$)-1 term already. And to get $x^n$ you need to fix an $n$ on both sides.2011-05-15
  • 0
    @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?2011-05-15
  • 0
    @muffel, what is?2011-05-15
  • 0
    @muffel, left hand side of what? Nobody knows what you're pointing at.2011-05-15
  • 0
    ok, sorry! I need to compare the coefficients of the term $$\sum\limits_{n = 0}^\infty \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 = \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)$$ and the only two things I don't come along that well are the different range of n once from 0 and once from 1 and the $x^n$ which I don't find in the expanded term of quanta.2011-05-15
  • 0
    @muffel, okay I added some extra notes, maybe that helps to show the relation between these two.2011-05-15
  • 0
    @quanta really great, thanks a lot!2011-05-15