1.2k views

How many different equivalence relations with exactly three equivalence classes are there on a set with 5 elements

1. 10
2. 15
3. 25
4. 30

edited | 1.2k views

• One Euivelence relation creates one partition.
• S = $\left \{ a,b,c,d,e \right \}$ ,here one possible parition is = $\left \{ \left \{ a,b \right \} , \left \{ c,d \right \} , \left \{ e \right \} \right \}$ . Tis partition has 3 groups. Corresponding EQ relation has 3 EQ classes. Note that this partition is unordered..
• So, no of different unordered partitions = No of equivalence relations.

Here the condition is we need only 3 equivalence classes. So, the partition has to be done in 3 unordered groups.

\begin{align*} \frac{5!}{1!1!3!}.\frac{1}{2!} + \frac{5!}{2!1!2!}.\frac{1}{2!} = 10 + 15 = 25 \\ \end{align*}

In case if we need maximum possible EQ relations on 5 elements.

\begin{align*} 5 &\rightarrow 5\Rightarrow \frac{5!}{5!} = 1\\ \\ \hline \\ &\rightarrow 4 \qquad 1 \Rightarrow \frac{5!}{4!1!} = 5 \\ \\ \hline \\ &\rightarrow 3 \qquad 2 \Rightarrow \frac{5!}{3!2!} = 10 \\ \\ \hline \\ &\rightarrow 3 \qquad 1 \qquad 1 \Rightarrow \frac{5!}{3!1!1!}*\frac{1}{2!} = 10 \\ \\ \hline \\ &\rightarrow 2 \qquad 2 \qquad 1 \Rightarrow \frac{5!}{2!2!1!}*\frac{1}{2!} = 15 \\ \\ \hline \\ &\rightarrow 2 \qquad 1 \qquad 1 \qquad 1 \Rightarrow \frac{5!}{2!1!1!1!}*\frac{1}{3!} = 10 \\ \\ \hline \\ &\rightarrow 1 \qquad 1 \qquad 1 \qquad 1 \qquad 1 \Rightarrow \frac{5!}{1!1!1!1!1!}*\frac{1}{5!} = 1 \\ \\ \hline \\ &\Rightarrow \text{Total} = 1+5+10+10+15+10+1 = 52 \end{align*}

The procedure for partitioning is , indistinguishable $\rightarrow$ indistinguishable but because of the distinct elements we need to further evaluation.

Graphically we were interested in the rectangle shown below containing 25 EQ relation or partitions.

answered by Veteran (56.9k points) 36 189 500
edited
This is also Bell Number for maximum case, right ?
yes :) $B_5$
thanks for ur detailed ans  , but why u have divided it by 2! in case of 3 1  1   and 2  2  1

and by 3!  in  2   1   1   1 and so on
if we have a set {a,b,c,d} and two indistinct boxes

To allocate {a,b,c,d}...two-and-two,  in those two boxes we have only 3 choices. $\frac{4!}{2!2!}*\frac{1}{2!} = 3$

those are $\left \{ \left \{ a,b \right \} ,\left \{ c,d \right \} \right \} , \ \left \{ \left \{ a,c \right \} ,\left \{ b,d \right \} \right \} , \ \left \{ \left \{ a,d \right \} ,\left \{ b,c \right \} \right \}$

No need to put a in box2 and count again. because boxes are indistinct.

In analogy to these boxes, those groups of a partition are also same,only the elements inside a group are distinct.

1
2