GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
153 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 (41.2k points)  
edited by | 153 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 (43.5k 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 Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,446 questions
26,759 answers
60,943 comments
22,955 users