Relations and Combinatorics exercise

Question

Be $A=\{1,2,3,\ldots,10\}$ Determine how many equivalence relations can be defined in $A$ with exactly two equivalence classes.

Determine how many equivalence relations can be defined in $A$ with exactly three equivalence classes.

What I did for two is:

$${10\choose1}+{10\choose2}+\cdots+{10\choose9}=\sum_{i=1}^9{10\choose i}=2^{10}-2$$

For three:

$$\text{ #(All the posible Classes)} - {10\choose1}{9\choose0}-{10\choose0}=2^{10}-11$$

is this ok? is there a easier way to do think it?

Answer 1

If the chosen subset is $\{1,2,3\}$, then it's the SAME equivalence relation as if the chosen subset is $\{4,5,6,7,8,9,10\}$. Therefore when you add $\dbinom{10}{3}+\dbinom{10}{7}$, you're counting each of those equivalence relations twice.

Similarly with $\dbinom{10}{1}+\dbinom{10}{9}$ and with $\dbinom{10}{2}+\dbinom{10}{8}$ and with $\dbinom{10}{4}+\dbinom{10}{6}$.

A different sort of thing happens with $\dbinom{10}{5}$. That one term alone counts each of $126$ equivalence relations twice: $\{1,2,3,4,5\}$ corresponds to the SAME equivalence relation as $\{6,7,8,9,10\}$.

So the answer is

$$\dfrac{\sum_{k=1}^9 \binom{10}{k}}{2} = \dbinom{10}{1} + \dbinom{10}{2} + \dbinom{10}{3} + \dbinom{10}{4} + \frac{\dbinom{10}{5}}{2} = 511$$

Answer 2

For two classes, instead of summing over binomial coefficients, just note that there are $2^{|A|}$ different subsets of $A$. Two of those ($\varnothing$ and $A$ itself) cannot be used as equivalence classes, but for the rest of them, each $B\subset A$ gives rise to an ordered pair of equivalence classes $(B,A\setminus B)$.

Each equivalence relation can described by such ordered pairs in exactly two ways, so the total number of classes is $\frac{2^{|A|}-2}{2}$. This almost matches what you've already got, except that you've forgotten to divide by two.

---

For three classes the same strategy can be used, though it is a bit more involved to subtract the choices that don't work.

First, there are $3^{|A|}$ ways to assign the labels a, b, and c to each of the elements of $A$. We have to subtract the assignments where a is never used -- there are $2^{|A|}$ of those -- the ones where b is never used ($2^{|A|}$) of those, and the ones where c is never used (yet $2^{|A|}$). But now the three combinations where everything has the same label have been subtracted twice each, so those have to be added back in. (This is just an instance of the inclusion-exclusion principle). Finally divide by the $3!$ ways to express each equivalence relation, because the order of the labels don't matter. We get $$ \frac{3^{|A|} - 3\cdot 2^{|A|} + 3}{3!} $$ equivalence relations with 3 classes.

Answer 3

An Equivalence relation (more precisely: The set of equivalence classes of this relation) over a finite set is isomorphic to a partition over this set. The number of $k$-partitions of a set $X, |X|=n$ are given by the Stirling numbers of the second kind and thus represent the number of equiv relations with a given number of equiv classes.