UGC NET CSE | June 2012 | Part 3 | Question: 50

Question

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?

• A. $2^{n(n+1)/2} \text{ and } 2^n.3^{n(n-1)/2}$
• B. $3^{n(n-1)/2} \text{ and } 2^{n(n-1)}$
• C. $2^{n(n+1)/2} \text{ and } 3^{n(n-1)/2}$
• D. $2^{n(n+1)/2} \text{ and } 2^{n(n-1)/2}$

Answer 1

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 n²-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= 2ⁿ*$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.

Comments

beautifully explained but on my web page i am getting symbols like $ ,sqr please confirm it , is it my browser prob on anything else

---

Thank you.Please refresh the page.it may be content loading problem.

Answer 2

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

Answer 3

Correct  Answer is (D).