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.