How many equivalence relations on S have exactly 3 equivalence classes?

Question

Let S = {1,2,3,4,5,6,7,8}. How many equivalence relations on S have exactly 3 equivalence classes?

The only idea I have is to use the formula for Stirling numbers of the second kind, which seems like an unnecessary amount of calculations. Thanks in advance for any help!

Answer 1

As I mentioned in the comments, we should count the number of surjective functions from $S$ to $\{1, 2, 3\}$. Every function uniquely defines an ordered partition of $S$ into $3$ parts. This will over-count the number of (unordered) partitions by a factor of $3!$, which correspond to the equivalence relations on $S$ with $3$ classes.

There are a total of $3^8$ possibly functions from $S$ to $\{1, 2, 3\}$. We need to subtract out the functions from $S$ to strict subsets $U$ of $\{1, 2, 3\}$. If $|U| = 1$, then there is only one function from $S$ to $U$: the constant function. There are three constant functions (one for each $U \subseteq \{1, 2, 3\}$ with $|U| = 1$).

If $|U| = 2$, then there are a total of $2^8$ functions from $S$ to $U$, including the two constant functions. Hence, the number of functions whose range is $U$ is $2^8 - 2$. There are three such subsets $U$ of $\{1, 2, 3\}$.

Therefore, the total number of equivalence relations on $S$ with $3$ classes is $$\frac{3^8 - 3 \cdot (2^8 - 2) - 3}{3!} = 966.$$

Answer 2

To cut straight to the answer ... That is exactly what the Stirling numbers of the second kind counts.

So https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Table_of_values ... just read off the value $S(8,3)= \color{red}{966}$.

Alternatively use the formula for these numbers \begin{eqnarray*} S(n,k) = \frac{1}{k!} \sum_{i=0}^{k} \binom{k}{i} i^{n}. \end{eqnarray*} Which gives exactly the same as Theo.