# 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\geq 1$, we have

 $B(n)=\sum_{k=0}^{n}S(n,k)\qquad\textrm{for }n\geq 1$

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

###### Proposition 1.
 $B(n+1)=\sum_{k=0}^{n}\binom{n}{k}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\leq j\leq n+1$ then we have $\binom{n}{j-1}$ 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:

 $\displaystyle B(n+1)$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{n+1}\binom{n}{j-1}B(n+1-j)$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{n+1}\binom{n}{n+1-j}B(n+1-j)$ $\displaystyle=$ $\displaystyle\sum_{k=0}^{n}\binom{n}{k}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.

Title Bell number BellNumber 2013-03-22 14:47:07 2013-03-22 14:47:07 aoh45 (5079) aoh45 (5079) 7 aoh45 (5079) Definition msc 05A18 msc 11B73 StirlingNumbersSecondKind