Understanding Equivalence Relations and Partitions

An equivalence relation on a set partitions the set into disjoint subsets called equivalence classes. The number of equivalence classes corresponds to the number of subsets in the partition. Therefore, finding the number of equivalence relations with exactly three equivalence classes on a set of five elements is the same as finding the number of ways to partition a set of 5 elements into 3 non-empty subsets.

Calculating Partitions with Stirling Numbers

This count is given by the Stirling numbers of the second kind, denoted as $S(n, k)$ or $\begin{Bmatrix} n \\ k \end{Bmatrix}$, which represents the number of ways to partition a set of $n$ elements into $k$ non-empty subsets.

We need to calculate $S(5, 3)$. The formula for Stirling numbers of the second kind is:

$S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$

For $n=5$ and $k=3$, the calculation is:

$S(5, 3) = \frac{1}{3!} \sum_{j=0}^{3} (-1)^{3-j} \binom{3}{j} j^5$

Let's expand the sum:

• For $j=0$: $(-1)^{3-0} \binom{3}{0} 0^5 = (-1)^3 \times 1 \times 0 = 0
• For $j=1$: $(-1)^{3-1} \binom{3}{1} 1^5 = (-1)^2 \times 3 \times 1 = 1 \times 3 \times 1 = 3
• For $j=2$: $(-1)^{3-2} \binom{3}{2} 2^5 = (-1)^1 \times 3 \times 32 = -1 \times 3 \times 32 = -96
• For $j=3$: $(-1)^{3-3} \binom{3}{3} 3^5 = (-1)^0 \times 1 \times 243 = 1 \times 1 \times 243 = 243

Now, substitute these values back into the formula:

$S(5, 3) = \frac{1}{6} (0 + 3 - 96 + 243)$

$S(5, 3) = \frac{1}{6} (150)$

$S(5, 3) = 25$

Result

Thus, there are 25 different ways to partition a set of 5 elements into exactly 3 non-empty subsets. This means there are 25 different equivalence relations with exactly three equivalence classes on a set with five elements.