GATE CSE 1997 | Question: 6.3

Question

The number of equivalence relations of the set $\{1,2,3,4\}$ is

• A. $15$
• B. $16$
• C. $24$
• D. $4$

Comments

The Bell triangle may be constructed by placing the number 1 in its first position. After that placement, the leftmost value in each row of the triangle is filled by copying the rightmost value in the previous row.  The remaining positions are the sum of the two values to the left and upper left of the position.

The n^th bell numbers are the leftmost number of n^th row.

---

thank u

---

ans: 1+7+6+1=15

---

@Mk Utkarsh bro, according to my understanding, last line in your comment is wrong. In place of word "leftmost", "rightmost" should be used [OR] you should write leftmost number of (n+1)th row . Please tell me know if i am wrong. Thank you

---

Source: Wikipedia, after reading your answer

There is no doubt left in my mind, that with this speed of contribution to gateoverflow,

students wont be needing any standard books

as everything is so well explained on GO

Love you all contributors.

---

For a noob like me.. Easy Explanation!

https://www.youtube.com/watch?v=iJF2kPFGTUo

---

Let A = {1, 2, 3, 4}

Each and every equivalence relation on A corresponds to one of the partition of A. In fact this mapping is Bijective.

Ref: https://www.geeksforgeeks.org/number-possible-equivalence-relations-finite-set/

---

Can we solve this question using graphs? My approach was to not take any vertices for all the nodes representing as a vertex and then eventually keep on adding the edges in the graph. But my answer is not matching.

---

Doubt:

equivalence class is nothing but the partitions on equivalence relation and as bell no. gives the total no of partitions on set of n elements and also no. of equivalence relations (Total no of partitions) so can we say that bell no. gives the total equivalence classes?​​​​​​

Answer 1

No. of Equivalence Relations on a set of $n$ elements is given by the $n^{th}$ BELL number $B_n$.

$B_{n}$ is also equal to the number of different ways to partition a set that has exactly $n$ elements, or equivalently, the number of equivalence relations on it.

Ref: https://en.wikipedia.org/wiki/Bell_number

$n^{th}$ Bell number can be found easily from the Bell triangle as follows:

Here, $E_{(i,j)} = E_{(i-1,j-1)}+E_{(i,j-1)}; i,j > 1,$
$\qquad E_{(1,1)} = 1, E_{(i,1)} = E_{(i-1,i-1)}$

$\begin{array}{ccc}1&&&&-\text{  No. of partitions for 1 element set}\\1 &2&&&-\text{  No. of partitions for 2 element set}\\2&3&5&&-\text{  No. of partitions for 3 element set}\\5&7&10&15&-\text{  No. of partitions for 4 element set}\end{array}.$

So, answer is (A) 15.

Comments

I tried to print all the equivalence relations on a set of three elements.

But the answer should be 5. What am I doing wrong. 

---

@neel19

Your R4 and R5 is not equivalence (because not transitive).

For example in R4 (3,1) and (1,2) is there. So, for transitive we must include (3,2) also. Now for symmetric we must include (2,3).  So, it will become R6 only.

Answer 2

Ways of selecting any of the following elements out of 4 : (i) 1 element : C(4,1) (ii) 2 elements : C(4,2) (iii) 3 elements : C(4,3) (iv) 4 elements : C(4,4)

Total partitions = C(4,1) + C(4,2) + C(4,3) + C(4,4) = 15

Comments

how to use this formula can you expalin it briefly i am not able to understand the solution of this question.

---

nice work brother, saves a lot of time, thank a lot

---

Lol, try this with {1,2,3,4,5} and see if you get 52.

Answer 3

Ans A. no. of equivalence relations  = no. of partition set possible  = 1 (all four elements) + 3(2 + 2 elements partition) + 4(3 + 1 element partition) + 6 (2 + 1 + 1 element partition)  + 1 (1 + 1+ 1+ 1 element partition) = 15

Comments

please explain in detail

---

it means applying combinatorics, but whats the underlying principle behind partitioning that is leading to equivalence??

i think this text is relevant : https://en.wikipedia.org/wiki/Bell_number

---

To understand this please watch videos of grouping and distribution. You will get it.

Answer 4

The Bell numbers satisfy a recurrence relation

:

Here B0 =B1=1

B2= 1C0*B0+1C1*B1 =1+1 =2

B3=2C0*B0+2C1*B1+2C2*B2=1+2+2 =5

B4=3C0*B0+3C1*B1+3C2*B2+3C3*B3=1+3+6+5 =15

Given set has 4 element so we just calculated B4 

Comments

awesome explanation tnx sir.