The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
5.7k views

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.5k points)
edited by | 5.7k views
0
For any Set that contains 4 elements then no of Equivalence relation=15.
+1

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.

4 Answers

+21 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.

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.

answered by Boss (42.8k 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.3k points)
edited by
0
@shekhar can u explain for n=5...
0
for 5 it would be

1

1  2

2  3  5

5 7 10 15

15 20 27 37  52
0

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,...so on.

0

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

Then why not true for n=3.

{a,b,c}

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

but the correct answer is 5.

please explain.

0
The formula which ur using is wrong

The formula is

To=summation of( n-1Ci * Tn-1-i) from(i=0 to n )
0
how to use this formula can you expalin it briefly i am not able to understand the solution of this question.
+19 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.6k points)
0
please explain in detail
+1
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
+5 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 (8k points)


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

39,848 questions
46,815 answers
141,154 comments
59,066 users