GATE CS 1997 Q6.3 — Monoids and Groups

There is a one-to-one correspondence between the equivalence relations on a set and the partitions of that set.

The number of partitions of a set of size $n$ is given by the $n$-th Bell number, denoted as $B_n$.

For a set of size $n = 4$, we can find $B_4$ using the Bell number recurrence relation:

Starting with $B_0 = 1$:

• $B_1 = \binom{0}{0} B_0 = 1$
• $B_2 = \binom{1}{0} B_0 + \binom{1}{1} B_1 = 1(1) + 1(1) = 2$
• $B_3 = \binom{2}{0} B_0 + \binom{2}{1} B_1 + \binom{2}{2} B_2 = 1(1) + 2(1) + 1(2) = 5$
• $B_4 = \binom{3}{0} B_0 + \binom{3}{1} B_1 + \binom{3}{2} B_2 + \binom{3}{3} B_3 = 1(1) + 3(1) + 3(2) + 1(5) = 15$

Alternatively, we can count the partitions of the set $\{1, 2, 3, 4\}$ by grouping them by their partition shapes:

1. Type $[4]$: $1$ partition of size $4$ (e.g., $\{\{1, 2, 3, 4\}\}$) $\rightarrow 1$
2. Type $[3, 1]$: Partitions with one subset of size $3$ and one of size $1$ $\rightarrow \binom{4}{3} = 4$
3. Type $[2, 2]$: Partitions with two subsets of size $2$ $\rightarrow \frac{1}{2} \binom{4}{2} = 3$
4. Type $[2, 1, 1]$: Partitions with one subset of size $2$ and two of size $1$ $\rightarrow \binom{4}{2} = 6$
5. Type $[1, 1, 1, 1]$: $1$ partition with four subsets of size $1$ $\rightarrow 1$

Summing these up: $1 + 4 + 3 + 6 + 1 = 15$.

Thus, the number of equivalence relations is 15.