next up previous contents
Next: Inclusion-Exclusion Principle Up: Special Sequences of Integers Previous: Catalan numbers   Contents

Bell numbers

Definition 8.6.12   The Bell number $ B_n$ is the number of partitions of $ \{1,\dots,n\}$.

It is obvious from the definitions that $ B_n = \sum_k S(n,k)$.

Lemma 8.6.13  

$\displaystyle B_{n+1} = \sum_{0 \le k \le n} \binom{n}{k} B_k

Proof. For, put the element $ n+1$ in with a $ k$-subset of $ \{1,\dots,n\}$ for $ k=0$ to $ k = n$. $ \qedsymbol$

There isn't a nice closed formula for $ B_n$, but there is a nice expression for its exponential generating function.

Definition 8.6.14   The exponential generating function that is associated with the sequence $ (a_n)_{n \in \mathbb{N}_0}$ is

$\displaystyle \Hat{A}(z) = \sum_n \frac{a_n}{n!} z^n.

If we have $ \Hat{A}(z)$ and $ \Hat{B}(z)$ (with obvious notation) and $ \Hat{A}(z) \Hat{B}(z) = \sum_n \frac{c_n}{n!} z^n$ then $ c_n = \sum_k \binom{n}{k} a_k b_{n-k}$, the exponential convolution of $ (a_n)_{n \in \mathbb{N}_0}$ and $ (b_n)_{n \in \mathbb{N}_0}$. Hence $ B_{n+1}$ is the coefficient of $ z^n$ in the exponential convolution of the sequences $ 1,1,1,1,\dots$ and $ B_0, B_1, B_2, \dots$. Thus $ \Hat{B}(z)' = e^z \Hat{B}(z)$. (Shifting is achieved by differentiation for exponential generating functions.) Therefore $ \Hat{B}(z) = e^{e^z + C}$ and using the condition $ \Hat{B}(0) = 1$ we find that $ C = -1$. So

$\displaystyle \Hat{B}(z) = e^{e^z - 1}.$    

root 2002-06-10