Consider a set $S$ with cardinality $s$. Prove that the number of equivalence relations on the set $S$ with exactly 5 distinct equivalence classes is:
$$
\frac{1}{5!}\sum^5_{i=0}(-1)^i{5\choose i}(5-i)^s.
$$
I know that there exists a bijection between equivalence relations on S and the number of partitions on that set. Since there are $s$ elements I must work out how many partitions there are of $s$. However, I am told there are $5$ equivalence classes so I understand there are ${5\choose i}$ ways. However I am confused as to where the rest comes from?
Best Answer
If there are $s$ elements, and they can each can be put into one of $5$ equivalence classes, then we get $s^5$ allocations. But we have some significant overcounting.
By this method, there may be some classes with no members, and this will not do. To make sure that we exclude those cases we need to apply inclusion-exclusion.
${5\choose 0} 5^s - {5\choose 1} 4^s + {5\choose 2} 3^s - {5\choose 3} 2^s + {5\choose 4} 1^s$
We also have a different sort of overcounting. Class 1 is not fundamentally different from class 2, etc. So, far we have treated them differently.
We need to divide by the number of permutations of the 5 classes.
$\frac {{5\choose 0} 5^s - {5\choose 1} 4^s + {5\choose 2} 3^s - {5\choose 3} 2^s + {5\choose 4} 1^s}{5!}$
Which is the same as your formula above.