How many equivalence relations can be defined on the set $S = {1, 2, 3, 4, 5}$ that partition $S$ into exactly three equivalence classes?

medium 3 marks Class 12 · Mathematics · Relations and Functions

Answer

The correct answer is 25 — Therefore, there are $25$ distinct equivalence relations that yield exactly three equivalence classes.

Step-by-step solution

An equivalence relation on a finite set corresponds to a partition of that set.
The number of ways to partition a set of $n$ elements into $k$ non‑empty unlabeled subsets is given by the Stirling number of the second kind $S (n, k)$ .
Here $n = 5$ and $k = 3$ , so we need $S (5, 3)$ .
Using the recurrence $S (n, k) = k S (n - 1, k) + S (n - 1, k - 1)$ or a known table, compute:
$S (4, 3) = 6$ and $S (4, 2) = 7$ .
Then $S (5, 3) = 3 \times S (4, 3) + S (4, 2) = 3 \times 6 + 7 = 25$ .
Therefore, there are $25$ distinct equivalence relations that yield exactly three equivalence classes.

Common mistake: Treating the three classes as ordered (counting permutations) which would give a larger number.

Concept tested: Counting equivalence relations via set partitions