# Ways to partition an n-element set

I've done a couple of searches and haven't found a solution to this here, but if I've missed it please feel free to close the question!

I was wondering how many different equivalence relations I could impose on a set with n-elements. Since each equivalence relation corresponds to a unique partition of the set, I assume this question reduces to figuring out how many ways there are to partition a set of n elements.

Word on the street is that these are the Bell Numbers, satisfying the cute recurrence relation $$B_{n+1}=\Sigma_{k=0}^n {n\choose k}B_k$$

I guess I just wanted some motivation, or some reverse engineering of the truth of this. It's not immediately obvious to me why the number of partitions should follow this formula. Also, is there a closed form of this? Pointing me to various sources that explain these things is also more than welcome.

-
If you take a look at en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, it may be of some use. –  Alex J Best Dec 17 '12 at 2:20

Rewrite the recurrence: $$B_{n+1}=\sum_{k=0}^n\binom{n}kB_k=\sum_{k=0}^n\binom{n}{n-k}B_k=\sum_{k=0}^n\binom{n}kB_{n-k}\;.$$
To form a partition of $[n+1]$, first fix the part containing $n+1$; say that it has $k$ other elements. There are $\binom{n}k$ ways to choose these other elements, and there are $B_{n-k}$ ways to partition the remaining $n-k$ elements of $[n+1]$, so there are $\binom{n}kB_{n-k}$ partitions of $[n+1]$ that have $n+1$ in a part with exactly $k$ other elements. Summing over the possible values of $k$ yields the recurrence.