The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 votes

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

  1. $15$
  2. $16$
  3. $24$
  4. $4$
asked in Set Theory & Algebra by Veteran (59.8k points)
edited by | 7.1k views
For any Set that contains 4 elements then no of Equivalence relation=15.

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 nth bell numbers are the leftmost number of nth row.

thank u

4 Answers

+29 votes
Best answer

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.


$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.

answered by Boss (43.6k points)
edited by
+39 votes

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

answered by Boss (45.6k points)
edited by
@shekhar can u explain for n=5...
for 5 it would be


1  2

2  3  5

5 7 10 15

15 20 27 37  52

shekhar chauhan "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)"

I think the method that you are using to calculate no of equivalence relation is not correct because it is not giving correct answer for n=5,n=6, on.


Sir,I have a confusion......

Then why not true for n=3.


by your formula 3C1 + 3C2 +3C3 =23-1=7

but the correct answer is 5.

please explain.

The formula which ur using is wrong

The formula is

To=summation of( n-1Ci * Tn-1-i) from(i=0 to n )
how to use this formula can you expalin it briefly i am not able to understand the solution of this question.
+21 votes
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
answered by Boss (13.7k points)
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 :
To understand this please watch videos of grouping and distribution. You will get it.
+12 votes

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 

answered by Loyal (8.5k points)
awesome explanation tnx sir.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,397 questions
53,564 answers
70,837 users