f the set.

Here, the set is $ S = \{1, 2, 3, \ldots, 10\} $. So, we must divide it into parts (subsets) such that the total number of elements across all parts is 10.

For an equivalence relation, if one class has $ n_i $ elements, then all possible ordered pairs inside this class are related. Hence, it contributes $ n_i^2 $ related pairs to the relation.

Because the total number of related pairs is given as 42, we need to find positive integers $ n_1, n_2, \ldots, n_k $ satisfying both:

$$ n_1 + n_2 + \ldots + n_k = 10 $$

and

$$ n_1^2 + n_2^2 + \ldots + n_k^2 = 42 $$

Now, we search for combinations of squares that add up to 42, while the corresponding numbers add up to 10.

Possible combinations are:

$$ 42 = 36 + 4 + 1 + 1 \ \Rightarrow \ \{6, 2, 1, 1\} $$

$$ 42 = 25 + 16 + 1 \ \Rightarrow \ \{5, 4, 1\} $$

Hence, the partitions can be $ \{6, 2, 1, 1\} $ and $ \{5, 4, 1\} $.

Case 1: Partition {5, 4, 1}

First choose 5 elements out of 10 for one class, then choose 4 out of the remaining 5 for the next class, and the last one forms a single-element class. The number of ways is:

$$ {^{10}C_5} \times {^{5}C_4} \times {^{1}C_1} = 1260 $$

Case 2: Partition {6, 2, 1, 1}

First choose 6 elements out of 10, then 2 from the remaining 4, and the last two each become single-element classes. Since the two single-element groups are identical, we divide by 2! to adjust for overcounting. So the number of ways is:

$$ {^{10}C_6} \times {^{4}C_2} \times \frac{{^{2}C_1 \times ^{1}C_1}}{2} = 1260 $$

Therefore, the total number of such equivalence relations is the sum of both cases:

$$ 1260 + 1260 = 2520 $$

Permutations And Combinations

Continue this paper

Similar Permutations And Combinations PYQs

More practice from this question