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

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.