[Math] Bell numbers (number of partitions of set of cardinality n) recurrence relation proof

combinatorics

Let $X$ be a set of cardinality $n$. How many partitions does it have? The users on the website found that these are the so called bell numbers. They also pointed out the following recurrence relation:

$$B_{n+1}=\sum\limits_{k=0}^n\binom{n}{k}B_k$$

Could someone provide some insight and prove this?

Best Answer

For concreteness, let's suppose we are partitioning the set $\{1, 2, \dots, n+1\}$. Focus first on the block containing the element $1$. Let $k$ denote the number of elements other than $1$ that belong to this block. We can choose these elements in $\binom{n}{k}$ ways. Having formed this block, we partition the remaining $n + 1 - (k + 1) = n -k$ elements in $B_{n-k}$ ways. Summing over $k$ gives $$ \sum_{k = 0}^n \binom{n}{k} B_{n-k}. $$ By the symmetry of the binomial coefficients, this expression is equivalent to $$ \sum_{k = 0}^n \binom{n}{k} B_{k}. $$

Related Question