$\begingroup$Let X be a finite set with |X| : 6. Then the number of equivalence relations on X such that each equivalence class has at least three elements in it is: (A) 10. (B) 11. (c) 20. (D) 21.
My try
We know there is a one to one correspondence between Equivalence Relation and Partitions. Thus, for any equivalence Relation such that each class has at least three elements in it implies the partition of 6 can be either
6 = 2+2+2 or 6 = 2+4 or 6=6.
(Since the partition involving 1 is a one element class.)
The number of ways to partition 6 into 2+2+2 = (6C2 x 4C2 x 2C2)/3! = 15
The number of ways to partition 6 into 2+4 = 6C2 = 15
The number of ways to partition 6 into 6 = 1
Thus , total equivalence Relation such that each class has at least three elements = 15+15+1 = 31
Please correct me where I have made wrong assumption.
$\endgroup$01 Answer
$\begingroup$In the $2+2+2$ case, each equivalence class has two elements and therefore not "at least three". A similar thing is true for $4+2$.
There are only two ways to do it. Either $6=6$ or $6=3+3$. Any other partition of $6$ necessarily has either a $2$ or a $1$ and is therefore invalid.
$\endgroup$1
