Bell numbers

**Bruno J.** · August 12th 2009, 09:12 PM

The nth Bell number $B_n$ is the number of partitions of a set having $n$ elements. The sequence begins $1,1,2,5,15,52...$ .

Show that the exponential generating function of the Bell numbers is

$G(z)=\sum_{n=0}^\infty B_n\frac{z^n}{n!} = e^{e^z-1}$

**PaulRS** · August 13th 2009, 08:28 AM

Lemma: Let $a_n(k)$ be the number of ordered partitions of a set of n elements in k sets. - or the number of ways in which you can distribute n balls into k boxes -
Then $\sum_{n=0}^{\infty}{\tfrac{a_n(k)}{n!}\cdot x^n}=(e^x -1)^{k}$

Proof

Let's compute the coefficient of $x^n$ of the RHS.

Since $e^x - 1 = x + {\textstyle{{x^2 } \over {2!}}} + ...$ it follows that our coefficient is: $ \sum\limits_{a_1 + ... + a_k = n} {{\textstyle{1 \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}} $

Now: $ \sum\limits_{a_1 + ... + a_k = n} {{\textstyle{{n!} \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}} = \sum\limits_{a_1 + ... + a_k = n} {{\textstyle{{\left( {a_1 + ... + a_k } \right)!} \over {\left( {a_1 !} \right) \cdot ... \cdot \left( {a_k !} \right)}}}} $ and each term is the number of ordered permutations in which you can have $a_1$ elements in box number 1, ... -permutations with repetition

-

So the coefficient is actually ${\textstyle{{a_n \left( k \right)} \over {n!}}}$ $\square$

Next note that $ \left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\} = {\textstyle{1 \over {k!}}} \cdot a_n \left( k \right) $ -the LHS is the stirling number of the second kind, or, the number of partitions of a set of n elements into k sets (here we do not care about the order) -

Hence: $ \sum\limits_{n = 0}^\infty {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\} \cdot {\textstyle{{x^n } \over {n!}}}} = {\textstyle{{\left( {e^x - 1} \right)^k } \over {k!}}} $ and summing over k : $ e^{e^x - 1} = \sum\limits_{k \ge 0} {{\textstyle{{\left( {e^x - 1} \right)^k } \over {k!}}}} = \sum\limits_{k \ge 0} {\sum\limits_{n \ge 0} {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\} \cdot {\textstyle{{x^n } \over {n!}}}} } = \sum\limits_{n \ge 0} {\left( {\sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\}} } \right) \cdot {\textstyle{{x^n } \over {n!}}}} \$

Since: $ B_n = \sum\limits_{k \ge 0} {\left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right\}} $ we are done $\square$

**Bruno J.** · August 13th 2009, 09:27 AM

Very nice!
Here is my proof.

First notice that the Bell numbers are of "binomial type"; i.e. they satisfy the recurrence $B_{n+1}=\sum_{j=0}^n{n \choose j}B_j$ . You can see that by induction, considering where to put the $(n+1)^{\mbox{st}}$ object; it can belong to a part by itself (in $B_n$ different ways), or it can belong to a two-object part with ${n \choose 1}$ choices for the other object and $B_{n-1}$ ways to partition the remaining objects, etc.

Now let $G(z)$ be the generating function. Differentiating is equivalent to shifting the sequence one place to the left. Moreover, multiplying by $e^z$ is equivalent to taking the binomial convolution : if $f(z)=\sum_{j=0}^\infty a_j\frac{z^j}{j!}$ then the coefficient of $\frac{z^n}{n!}$ in $e^zf(z)$ is $\sum_{j=0}^n{n \choose j}a_j$ .

So we know that the generating function satisfies the differential equation $G'(z)=e^zG(z)$ . So $G(z)=e^{e^z+C}$ . Since we have $G(0)=1$ , we must have $C=-1, \: \: G(z)=e^{e^z-1}$

Thread: Bell numbers

LinkBack

Thread Tools

Display

Bell numbers

Similar Math Help Forum Discussions

software for bell curve graphs

Bell Curves

bell numbers

Computing Bell Number for set of n elements.

bell curve

Search Tags