7.4k views

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

1. $15$
2. $16$
3. $24$
4. $4$
edited | 7.4k views
+13

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.

0
thank u
0

ans: 1+7+6+1=15

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

edited by

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

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

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.
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
0
+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
0
To understand this please watch videos of grouping and distribution. You will get it.

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

0
awesome explanation tnx sir.

1
2