GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
654 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

 

asked in Set Theory & Algebra by Veteran (44.5k points)  
edited by | 654 views
25 is the answer ??
yes explain plz

1 Answer

+8 votes
Best answer
  • 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 (50.9k points)  
edited by
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.


Top Users Aug 2017
  1. Bikram

    4902 Points

  2. ABKUNDAN

    4704 Points

  3. akash.dinkar12

    3480 Points

  4. rahul sharma 5

    3158 Points

  5. manu00x

    3012 Points

  6. makhdoom ghaya

    2470 Points

  7. just_bhavana

    2388 Points

  8. stblue

    2138 Points

  9. Tesla!

    2060 Points

  10. joshi_nitish

    1758 Points


25,014 questions
32,139 answers
74,821 comments
30,185 users