GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
292 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 (43.5k points)  
edited by | 292 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 (46.8k 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 May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1616 Points

  3. sh!va

    1580 Points

  4. Arjun

    1336 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1028 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    972 Points

  9. LeenSharma

    810 Points

  10. srestha

    662 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    242 Points

  2. Ahwan

    138 Points

  3. joshi_nitish

    112 Points

  4. jjayantamahata

    104 Points

  5. Arjun

    64 Points


22,725 questions
29,056 answers
65,053 comments
27,566 users