# Bell Numbers: How to put EGF $e^{e^x-1}$ into a series?

I'm working on exponential generating functions, especially on the EGF for the Bell numbers $B_n$.

I found on the internet the EGF $f(x)=e^{e^x-1}$ for Bell numbers. Now I tried to use this EGF to compute $B_3$ (should be 15). I know that I have to put the EGF into a series and have a look at the coefficients. Using $e^{f(x)}=1+f(x)+\frac{f(x)^2}{2!}+\frac{f(x)^3}{3!}+\ldots$ I get

\begin{eqnarray*} e^{e^x-1}&=&1+(e^x-1)+\frac{(e^x-1)^2}{2!}+\frac{(e^x-1)^3}{3!}\\ &=&1+e^x-1+\frac{e^{x^2}-2e^x+1}{2!}+\frac{e^{x^3}-3e^{x^2}+3e^x-1}{3!}\\ &=&e^x+\frac{e^{x^2}}{2!}-e^x+\frac{1}{2!}+\frac{e^{x^3}}{3!}-\frac{e^{x^2}}{2!}+\frac{e^{x}}{2!}-\frac{1}{3!}\\ &=&\frac{e^{x}}{2!}+\frac{e^{x^3}}{3!}-\frac{1}{2!}+\frac{1}{3!}\\ &=&\frac{1}{2!}e^x+\frac{1}{3!}e^{x^3}-\frac{1}{3}\\ &=&\frac{1}{2!}\left( 1+x^2+\frac{x^4}{2!}+\frac{x^8}{3!} \right)+\frac{1}{3!}\left( 1+x^3+\frac{x^6}{2!}+\frac{x^9}{3!}\right)\\ &=&\frac{1}{2}+\frac{x^2}{2}+\frac{x^4}{4}+\frac{x^8}{24}+\frac{1}{6}+\frac{x^3}{3!}+\frac{x^6}{12}+\frac{x^9}{36}\\ &=&\frac{1}{2}+\frac{x^2}{2}+\frac{x^3}{6}+\ldots \end{eqnarray*}

I think I can stop here, because the coefficient in front of $\frac{x^3}{3!}$ is not $15$.

Perhaps someone can help me out and give a hint to find my mistake?

-
$\left(\exp(x)\right)^2 = \exp(2 x) \not= \exp(x^2)$ – Sasha Jan 28 '13 at 17:25
$B_3=5$ and $B_4=15$. – Michael Hardy Jan 28 '13 at 17:26
@Michael Hardy: Yes you're right, but doesn't matter, because the coefficient in front of $\frac{x^4}{4!}$ is 15 neither. – ulead86 Jan 28 '13 at 17:27
@Sasha Thanks, I'll try it again. – ulead86 Jan 28 '13 at 17:28

It's probably easiest to expand the exponential in the exponent first, since that will lead to a finite number of terms to be evaluated:

\begin{align}e^{(e^x-1)} &= \exp\left(x+\frac{x^2}{2}+\frac{x^3}{6}+O(x^4)\right)\\ &=1+\left(x+\frac{x^2}{2}+\frac{x^3}{6}+O(x^4)\right) +\frac{1}{2}\left(x+\frac{x^2}{2}+\frac{x^3}{6}+O(x^4)\right)^2 +\frac{1}{6}\left(x+\frac{x^2}{2}+\frac{x^3}{6}+O(x^4)\right)^3+O(x^4)\\ &=1+\left(x+\frac{x^2}{2}+\frac{x^3}{6}+O(x^4)\right)+\frac{1}{2}\left(x^2+2(x)\left(\frac{x^2}{2}\right)+O(x^4)\right)+\frac{1}{6}\left(x^3+O(x^4)\right)\\ &=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^2}{2}+\frac{x^3}{2}+\frac{x^3}{6}+O(x^4)\\ &=1+x+x^2+\frac{5x^3}{6}+O(x^4) \end{align} From which the coefficients can be read off straightforwardly.

-
Thats nuch easier. Tanks a lot. – ulead86 Jan 28 '13 at 21:02

\begin{align} e^{e^x-1}&= 1+(e^x-1)+\frac{(e^x-1)^2}{2!}+\frac{(e^x-1)^3}{3!}+\cdots+\frac{(e^x-1)^n}{n!}+ \cdots \\[8pt] &= \cdots\cdots+\frac{e^{nx}+xe^{(n-1)x}+\binom n2 e^{(n-2)x}+\cdots+ne^x + 1}{n!}+ \cdots\cdots \end{align} One of the terms in the expansion of $(e^x-1)^n$ is $e^x$. When that is expanded, one of the terms will be $x^4/4!$. No matter how big $n$ is, you don't run out of terms involving $x^4$. So you don't just get finitely many terms involving $x^4$ and add up their coefficients to see if you get $\dfrac{15x^4}{4!}$. Rather, you get an infinite series.

The Wikipedia article titled Exponential formula gives a power series expansion of $$e^{f(x)}= \cdots+\frac{b_n x^n}{n!}+\cdots$$ when the power series expansion of $$f(x) = a_1+\frac{a_2 x^2}{2!}+\cdots+\frac{a_n x^n}{n!}+\cdots$$ is known. Notice this from the article: $$b_3 = a_3+3a_2 a_1 + a_1^3$$ because there is one partition of the set $\{ 1, 2, 3 \}$ that has a single block of size $3$, there are three partitions of $\{ 1, 2, 3 \}$ that split it into a block of size $2$ and a block of size $1$, and there is one partition of $\{ 1, 2, 3 \}$ that splits it into three blocks of size $1$. Apply that to $4$: $$b_4 = a_4 + 4a_3a_1 + 3a_2^2+6a_2a_1^2 + a_1^4$$ since there is one partition of the set $\{1,2,3,4\}$ that has a single block of size 4; there are four partitions into a block of size $3$ and a block of size $1$; three are three partitions into two blocks of size $2$; there are six partitions into a block of size $2$ and two blocks of size $1$; and there is one partition into four blocks of size $1$.

Wikipedia's article titled Dobinski's formula treats the expansion of each individual Bell number as an infinite series.

There is also Faà di Bruno's formula one the derivatives of composite functions.

-
Ok, but how do I find out the 3rd Bell number with EGF then? – ulead86 Jan 28 '13 at 17:41
I've added a link to a Wikipedia article that deals with this. – Michael Hardy Jan 28 '13 at 17:41

\begin{eqnarray*} e^{e^x-1}&=&1+(e^x-1)+\frac{(e^x-1)^2}{2!}+\frac{(e^x-1)^3}{3!}\\ &=&1+e^x-1+\frac{e^{2x}-2e^x+1}{2!}+\frac{e^{3x}-3e^{2x}+3e^x-1}{3!}\\ &=&e^x+\frac{e^{2x}}{2!}-e^x+\frac{1}{2!}+\frac{e^{3x}}{3!}-\frac{e^{2x}}{2!}+\frac{e^{x}}{2!}-\frac{1}{3!}\\ &=&\frac{e^{x}}{2!}+\frac{e^{3x}}{3!}-\frac{1}{2!}+\frac{1}{3!}\\ &=&\frac{1}{2!}e^x+\frac{1}{3!}e^{3x}-\frac{1}{3}\\ &=&\frac{1}{2!}\left( 1+x+\frac{x^2}{2!}+\frac{x^3}{3!} \right)+\frac{1}{3!}\left( 1+3x+\frac{9x^2}{2!}+\frac{27x^3}{3!}\right)-\frac{1}{3}\\ &=&\frac{1}{2}+\frac{x}{2}+\frac{x^2}{4}+\frac{x^3}{24}+\frac{1}{6}+x+\frac{3x^2}{4}+\frac{9x^3}{12}-\frac{1}{3}\\ &=&\frac{2}{3}+\frac{3x}{2}+\frac{5x^2}{4}+\frac{9x^3}{12}+\ldots \end{eqnarray*}

-
This gives the wrong value for every coefficient. – Steven Stadnicki Jan 28 '13 at 18:10

You probably don't want to use the series expansion for the exponential as you've done, because you will receive contributions to each coefficient from all orders of this expansion, so you'll still have infinite sums left to evaluate. Instead, you should use the fact that term $n$ in a sequence is given by $F^{(n)}(0)$, where $F(x)$ is the sequence's exponential generating function (and $F^{(n)}$ is the $n$-th derivative of $F$). If $F(x)=e^{f(x)}$, then its derivatives are given by $$F(0)=e^{f(0)} \\ F'(0)=f'(0)e^{f(0)} \\ F''(0)=(f''(0)+f'(0)^2)e^{f(0)} \\ F'''(0)=(f'''(0)+3f''(0)^2 f'(0) + f'(0)^3)e^{f(0)} \\ F^{(4)}(0)=(f^{(4)}(0)+f'''(0)f'(0)+6f'''(0)f''(0)f'(0)+3f''(0)^2+3f''(0)f'(0)^2+f'(0)^4)e^{f(0)}$$ and so on. If $f(x)=e^x-1$, then $e^{f(0)}=1$ and $f^{(n)}(0)=1$ for any $n \ge 1$. Adding up the terms, then, you have $B_0=B_1=1$, $B_2=2$, $B_3=5$, $B_4=15$, and so on.

-