> [!NOTE] Lemma > For a natural number $k$, $B_{k} = \sum_{n=0}^{k-1} \binom{k-1}{n} B_{n}$where $B_{k}$ denotes a [[Bell Numbers|Bell number]] (the number of partitions of $[k]$). ###### Combinatorial Proof Given a set partition of $[k]$, one of the parts - call it $S$ - contains the element 1. Let $n$ be the number of elements in $[k] \backslash S$. Then $0 \leq n \leq k-1$. If we know which $n$ elements they are, and how they are partitioned, it allows us to uniquely reconstruct the original set partition. The $n$ elements $[k]\setminus S$ form a subset of size $n$ of $\{2, \ldots, k\}$, so there are $\binom{k-1}{n}$ choices for what they are. Given such a choice, there are $B_n$ choices for how $[k]\setminus S$ is partitioned. This proves the formula.