How many different equivalence relations with exactly three different…
2016
How many different equivalence relations with exactly three different equivalence classes are there on a set with five elements ?
- A.
10
- B.
15
- C.
25
- D.
30
Attempted by 261 students.
Show answer & explanation
Correct answer: C
Answer: 25.
Key idea: Equivalence relations on a set correspond to partitions of the set into unlabeled nonempty blocks. So count the partitions of a 5-element set into exactly 3 blocks (this is the Stirling number S(5,3)).
Case 3+1+1: choose the 3-element block in C(5,3) = 10 ways. The remaining two elements are singletons, so this yields 10 partitions.
Case 2+2+1: choose the singleton in C(5,1) = 5 ways. The remaining 4 elements must be split into two unordered pairs; choose a pair in C(4,2) = 6 ways but divide by 2 because the two pairs are unlabeled, giving 6/2 = 3 pairings. This case yields 5 * 3 = 15 partitions.
Total = 10 + 15 = 25.
Therefore, there are 25 distinct equivalence relations on a 5-element set that produce exactly three equivalence classes.