# 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)$ | $=$ | $\sum _{j=1}^{n+1}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{j-1}}\right)B(n+1-j)$ | ||

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

$=$ | $\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.

Title | Bell number |
---|---|

Canonical name | BellNumber |

Date of creation | 2013-03-22 14:47:07 |

Last modified on | 2013-03-22 14:47:07 |

Owner | aoh45 (5079) |

Last modified by | aoh45 (5079) |

Numerical id | 7 |

Author | aoh45 (5079) |

Entry type | Definition |

Classification | msc 05A18 |

Classification | msc 11B73 |

Related topic | StirlingNumbersSecondKind |