edited by
21,138 views
54 votes
54 votes

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

  1. $15$
  2. $16$
  3. $24$
  4. $4$
edited by

6 Answers

Best answer
56 votes
56 votes

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.

edited by
54 votes
54 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

edited by
31 votes
31 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
20 votes
20 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 

Answer:

Related questions

42 votes
42 votes
2 answers
2
24 votes
24 votes
4 answers
3
Kathleen asked Sep 29, 2014
7,428 views
In the lattice defined by the Hasse diagram given in following figure, how many complements does the element ‘$e$’ have?$2$$3$$0$$1$