Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

There isn’t a nice closed form; see Wikipedia for a not so nice expression involving Stirling numbers of the second kind and for asymptotic results.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.