How many elements are there in the set R?

Question

+Let A
be a finite set with $n \geq 4$ elements and let R be an equivalence relation on A . Suppose that there are exactly $n-2$ equivalence classes and that no equivalence class can contain exactly three elements. Recall that the elements of the set R are ordered pairs of elements from A.

I know the answer is $n+4$ but I don't see the intuition behind it.

Answer 1

You can use the pidgeonhole principle to figure out exactly how many elements are in each equivalence class. In particular, if you (correctly) answer the two questions:

• Can there be any equivalence class with more than $3$ elements?
• How many equivalence classes must have exactly $2$ elements?

Then you know pretty much everything about the structure of the relation. Then, notice that $R$ is just the set of pairs which come from the same equivalence class - so for, instance, an equivalence class of size $2$ is represented by $2^2=4$ elements in $R$.

Answer 2

The answer is not $n-4$. Our group of $n$ people will be divided into $n-2$ groups, of which $n-4$ will be groups of $1$, and $2$ are groups of $2$. The $4$ people who will have company can be cosen in $\binom{n}{4}$ ways, and for each such way the chosen $4$ can be divided into $2$ groups of $2$ in $3$ ways.