Identities about Bell numbers

Question

The $n$-th Bell number equals the number of set partitions of $\{1,2,\dots,n\}$. We set $B_0 := 1$. Prove the following identities: $$B_n = \sum_{k=0}^{n}S_{n,k} \qquad and \qquad B_{n+1} = \sum_{k=0}^{n}\binom{n}{k}B_k$$

I don't exactly know what Bell numbers are. I checked their definition, it was something like the number of partitions, but it was a bit vague to me. I still don't get what's its connection to Stirling numbers and binomial coefficient. Any ideas with the problem?

Answer 1

HINT: Let $[n]=\{1,2,\ldots,n\}$. $B_n$ is the number of partitions of $[n]$ into any number of parts; $S_{n,k}$ is the number of partitions of $[n]$ into exactly $k$ parts.

For the second part of the question, suppose that you have a partition of $[n+1]$. One of its parts must contain the number $n+1$; call that part $P$. Let $k=|[n+1]\setminus P|$. Now think about these questions:

• What are the possible values of $k$?
• How many ways are there to choose $k$ elements other than $n+1$?
• How many partitions of $k$ elements are there?