Let S = \1, 2, 3, , 10\ . Consider the set X = \R : R is an equivalence relation on the set S such that R has exactly 42 elements\ . Then the number of elements in X is .
Answer
2520
Solution
An equivalence relation = partition of S into classes of sizes ni; |R| = ni2 with ni = 10.
ni2 = 42 ni(ni - 1) = 32, where n(n - 1) = 0, 2, 6, 12, 20, 30 for n = 1, , 6.
With total size 10, only 30 + 2 (sizes 6, 2, 1, 1) and 20 + 12 (sizes 5, 4, 1) work.
Sizes 6, 2, 1, 1: 10!6! 2! 1! 1! 2! = 1260
Sizes 5, 4, 1: 10!5! 4! 1! = 1260
Total = 2520
Answer: 2520