recategorized by
3,365 views
3 votes
3 votes

How many relations are there on a set with n elements that are symmetric and a set with n elements that are reflexive and symmetric?

  1. $2^{n(n+1)/2} \text{ and } 2^n.3^{n(n-1)/2}$
  2. $3^{n(n-1)/2} \text{ and } 2^{n(n-1)}$
  3. $2^{n(n+1)/2} \text{ and } 3^{n(n-1)/2}$
  4. $2^{n(n+1)/2} \text{ and } 2^{n(n-1)/2}$
recategorized by

3 Answers

Best answer
5 votes
5 votes

Let's Take a Example

A={1,2,3}

A $\times$ A ={ (1,1)(2,2)(3,3)(1,2)(2,1)(1,3)(3,1)(2,3)(3,2) } 

Symmetric Relation:- A relation 'R' on set A is said to be symmetric if (xRy)   then   (yRx) ∀x,y∈A

$\underbrace{(1,1)(2,2)(3,3) }_{n}$$\underbrace{(1,2)(2,1)(1,3)(3,1)(2,3)(3,2) }_{n^{2}-n}$

For n diagonal elements (1,1)(2,2)(3,3) there are 2 choices for each.Either it can include in relation or it can't include in relation.

For remaining n2-n elements according to definition of symmetric relation we can form pairs of(1,2)(2,1) and (1,3)(3,1)and (2,3)(3,2).For each pair there are 2 choices.Either it can include in relation or it can't not include in relation.

Hence,Total Number of Symmetric Relation= 2n*$2^{\frac{(n^{2}-n)}{2}}$=$2^{\frac{n(n+1)}{2}}$

Now For Reflexive and Symmetric relation there are only one choices for diagonal elements (1,1)(2,2)(3,3) and

for remaining.we can form pairs of(1,2)(2,1) and (1,3)(3,1)and (2,3)(3,2).For each pair there are 2 choices.Either it can include in relation or it can't not include in relation.

 
Hence,Total Number of Reflexive and Symmetric Relation = $2^{\frac{(n^{2}-n)}{2}}$=$2^{\frac{n(n-1)}{2}}$
 
 
 
Hence,Option(D)$2^{\frac{n(n+1)}{2}}$ and $2^{\frac{n(n-1)}{2}}$ is the correct choice.
selected by
5 votes
5 votes

Answer : 2^n(n+1)/2 and 2^n(n-1)/2

No of Symmetric Relation on a set are 2^n(n+1)/2

Reference : is Here with Explanation

No of reflexive and symmetric relation on a set are 2^n(n-1)/2

Reference : is Here with Explanation

edited by
0 votes
0 votes
Correct  Answer is (D).
Answer:

Related questions

5 votes
5 votes
1 answer
1
go_editor asked Jul 8, 2016
1,846 views
Let a*H and b*H be two cosets of H.Either a*H and b*H are disjointa*H and b*H are identicalThen,Only I is trueOnly II is trueI or II is trueI and II is false