Bell Number as Summation over Lower Index of Stirling Numbers of the Second Kind

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $B_n$ be the Bell number for $n \in \Z_{\ge 0}$.

Then:

$B_n = \displaystyle \sum_{k \mathop = 0}^n {n \brace k}$

where $\displaystyle {n \brace k}$ denotes a Stirling number of the second kind.


Corollary

When $n > 0$, the slightly simpler form can be used:

$B_n = \displaystyle \sum_{k \mathop = 1}^n {n \brace k}$


Proof

By definition of Bell numbers:

$B_n$ is the number of partitions of a (finite) set whose cardinality is $n$.


First consider the case where $n > 0$.

From Number of Set Partitions by Number of Components, the number of partitions of $S$ into $k$ components is $\displaystyle {n \brace k}$.

Thus the total number of all partitions of $S$ is the sum of $\displaystyle {n \brace k}$ where $k$ runs from $1$ to $n$.

Hence:

$B_n = \displaystyle \sum_{k \mathop = 1}^n {n \brace k}$

But $\displaystyle {n \brace 0} = 0$ for all $n \in \Z_{> 0}$, and so:

$B_n = \displaystyle \sum_{k \mathop = 0}^n {n \brace k}$


Now consider the edge case where $n = 0$, that is, $S = \O = \set{}$.

There is by conventional definition one partitions of $\O$, that is: $\set {\O}$

In this case, we have:

$\displaystyle {0 \brace 0} = 1$

and so:

$B_0 = \displaystyle \sum_{k \mathop = 0}^0 {n \brace k} = {0 \brace 0} = 1$

$\blacksquare$