How many equivalence relations on $\{a,b,c,d,e,f\}$ have $3$ equivalence classes?

Question

How many equivalence relations on $A=\{a,b,c,d,e,f\}$ have exactly $3$ equivalence classes?

My answer is $90$ -- I counted in three cases based on whether the partitions were split 4-1-1, 3-2-1, or 2-2-2. But my teacher said that the answer was $180$.

Please give me an explanation. Thanks in advance.

Answer 1

You are correct. There are $\{^6_3\}=90$ equivalence relations on a six-element set that has 3 equivalence classes.

For reference, those are Stirling numbers of the second kind. Similar to how binomial coefficients count subsets of a given size, $\{^n_k\}$ represents the number of partitions with a given number of non-empty parts. And similar to Pascal's identity, you can show the following recurrence relation:

$$\left\{{{n+1}\atop k}\right\}=k\left\{{n\atop k}\right\}+\left\{{n\atop {k-1}}\right\}$$

with $\left\{{0\atop 0}\right\}=1$ and $\left\{{n\atop 0}\right\}=\left\{{0\atop n}\right\}=0$ otherwise.

Answer 2

We count the number of ways of choosing the equivalence classes.

The sizes of the equivalence classes have to be: 4,1,1 or 3,2,1 or 2,2,2.

There are ${6\choose2}$ ways with 4,1,1. [Uniquely determined by picking the two items in size 1 classes]

There are $4{6\choose2}$ ways with 3,2,1 [${6\choose2}$ ways of picking the class size 2, then 4 of picking the class size 1.]

There are 15 ways with 2,2,2: 5 ways of picking the partner of $a$, then 3 ways of dividing the remaining 4.

Hence total 90.