Bell number

The Bell number, denoted $B(n)$ is the total number of partitions of a set with $n$ elements. For $n=0$, we have $B(0)=1$. For $n\ge 1$, we have

$$B(n)=\sum _{k=0}^{n}S(n,k)\mathit{\hspace{1em}\hspace{1em}}\text{for }n\ge 1$$

where $S(n,k)$ are the Stirling numbers of the second kind.

Proposition 1.

$$B(n+1)=\sum _{k=0}^n\left(\genfrac{}{}{0pt}{}{n}{k}\right)B(k)$$

Proof.

We count the number of partitions of a set of $n+1$ elements, depending on the size of the block containing the $n+1$st element. If the block has size $j$ for $1\le j\le n+1$ then we have $\left(\genfrac{}{}{0pt}{}{n}{j-1}\right)$ choices for the $j-1$ other elements of the block. The remaining $n+1-j$ elements can be partitioned in $B(n+1-j)$ ways. We have therefore that:

$B(n+1)$$=$${\displaystyle \sum _{j=1}^{n+1}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{j-1}}\right)B(n+1-j)$

$=$${\displaystyle \sum _{j=1}^{n+1}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{n+1-j}}\right)B(n+1-j)$

$=$${\displaystyle \sum _{k=0}^n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)B(k)$

∎

Using the formula above, one can easily derive the first few Bell numbers. Starting with $n=0$, the first ten Bell numbers are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147.