Partitions of a set with n elements (proof)

Question

I was reading a textbook about combinatorial mathematic which claimed that we can calculate the exact possible partitions of a set with n elements . I searched it on wikipedia and I read about bell number and summation formulas;

The first one which The Bell numbers satisfy a recurrence relation involving binomial coefficients : $$B_{n+1}=\sum\limits_{k=0}^{n} \binom{n}{k} B_k.$$

The second one is A different summation formula represents each Bell number as a sum of Stirling numbers of the second kind :

$$B_n=\sum\limits_{k=0}^{n} \left\{n \atop k\right\}.$$

Can you help me where the first one come from ?

And help me prove it through?

Answer 1

The Stirling number of the second kind $S(n,k)$ is the number of partitions of a set with $n$ elements into $k$ nonempty subsets. Summation over all $k$ gives the Bell number.

Answer 2

For the first equation, it might be easier to see what's going on if we rewrite the equation as $$B_{n+1}=\sum\limits_{k=0}^{n} \binom{n}{n-k} B_k$$ (Remember that $\binom{n}{k}=\binom{n}{n-k}$ by matching each subset with its complement) and then rewrite is again as $$B_{n+1}=\sum\limits_{k=0}^{n} \binom{n}{k} B_{n-k}.$$ (by reversing the order of the sum).

This allows us to contextualise the right hand side of the equation as the follows. In order to construct a partition of the set of $n+1$ elements, we will:

• First, decide how many other elements, $k$, are in the same partition as the element $n+1$. $k$ can run from $0$ ($n+1$ is in a part by itself) to $n$ (all of the other $n$ elements are in the same part as $n+1$: that part is the entire set).

• Second, decide which subset of $k$ elements we want to include in the part with $n+1$. There are $\binom{n}{k}$ ways to pick this subset.

• Finally, choose the partition of the remaining $n-k$ elements.

A partition of $n+1$ elements is uniquely determined by the part containing $n+1$ and how the rest of the elements are partitioned so this method gives us all possible partitions of $n+1$ elements.