MHB Different Number of Equivalence Relations

[Yankel]

Hello all,

I have a few questions related to the different number of equivalence classes under some constraint. I don't know how to approach them, if you could guide me to it, maybe if I do a few I can do the others. Thank you.

Given the set A={1,2,3,4,5},

1) How many different equivalence relations are there on A, with two equivalence classes?

2) How many different equivalence relations are there on A, with no three equivalence classes (other number rather than 3)?

3) How many different equivalence relations are there on A, which includes the pair (1,3) ?

4) How many different equivalence relations are there on A, with three equivalence classes?

I do not know how to approach this kind of questions. Can you please assist and give me some guidance ?

Thank you in advance.

 

[Evgeny.Makarov]

1) How many different equivalence relations are there on A, with two equivalence classes?

As many as there are nonempty subsets of $A$ (the other class is the complement of the subset).

4) How many different equivalence relations are there on A, with three equivalence classes?

The number 5 can be represented as a sum of three nonincreasing numbers (integer partitions of size 3) as follows.
\begin{align}
5&=3+1+1\\
5&=2+2+1
\end{align}
The first way corresponds to $\binom{5}{3}$ equivalence relations and the second one corresponds to $\binom{5}{2}\binom{3}{2}/2$ (please check).

2) How many different equivalence relations are there on A, with no three equivalence classes (other number rather than 3)?

This can be done similarly by considering all integer partitions of 5. You can verify your answer because the total number of equivalence relations on a set with $n$ elements is given by the Bell numbers.

3) How many different equivalence relations are there on A, which includes the pair (1,3) ?

So 1 and 3 must be in the same equivalence class. It may contain other elements; the total number of variants for this class is 8. If the class is just $\{1,3\}$, then we have to break $\{2,4,5\}$ into 1, 2 or 3 classes. If the class containing 1 and 3 has one extra element, then we have to break the two remaining elements into 1 or 2 classes: this makes 2 variants, and so on.

 

[Yankel]

I am slightly confused. I'll try to clear things.

I figured out that the number of ways to construct 2 equivalence classes is 15. Two equivalence classes will happen when one has one element and the other 4, or 2 and 3, for example: {1} and {2,3,4,5} or {1,2} and {3,4,5}. 5C2 + 5C1 gives 10+5=15.

Now I am trying to do the same thing for 3 equivalence classes. This can happen either when I have, for example, {1}, {2} , {3,4,5}, or, {1,2}, {3,4}, {5}. I have tried figuring out how to calculate the number of possibilities for this happening. The final answer should be 15, I can't get it. There are 10 different triplets for the first case, and there are 6 doubles out of 4 in the second.

What I am saying is that I don't understand the calculation behind:

"The first way corresponds to (5C3) equivalence relations and the second one corresponds to (5C2)(3C2)/2 (please check)."

That you wrote.

One more thing that doesn't end up. In total there are 2^25 different equivalence relations. How come the total number of relations with n classes (n=1,...5) doesn't end up to this number ?

 

[Evgeny.Makarov]

I figured out that the number of ways to construct 2 equivalence classes is 15.

My response from post #2 should be corrected: the number of equivalence relations on $A$ with two classes equals half of the number of nontrivial subsets of $A$. A subset is nontrivial if it is nonempty and does not equal the whole $A$. We take half because pairs of classes $(C,A\setminus C)$ and $(A\setminus C,C)$ produce the same equivalence relation. This gives $(2^5-2)/2=15$, which agrees with your answer.

What I am saying is that I don't understand the calculation behind:

"The first way corresponds to (5C3) equivalence relations and the second one corresponds to (5C2)(3C2)/2 (please check)."

By the first way I mean splitting $A$ into a subset of 3 elements and two subsets of 1 element. Once we select a three-element subset, the partition is fixed (the other two elements go to two different classes). Therefore, the integer partition $5=3+1+1$ corresponds to (5C3) equivalence relations.

The partition $5=2+2+1$ means that we have to select 2 elements out of 5 and then 2 out of the remaining 3. The remaining 1 element goes into a class by itself. But each such partition can be obtained in two ways: e.g., first choosing {1, 2}, then {3, 4} or by first choosing {3, 4} and then {1, 2}.

One more thing that doesn't end up. In total there are 2^25 different equivalence relations.

I wrote that the total number of equivalence relations on a set with 5 elements is given by the Bell number $B_5=52$.

 

[Yankel]

Thank you very much !

All clear now !