Question 9017 – GATE 2010

Definition of Reflexive relation:

A relation ‘R’ is reflexive if it contains xRx ∀ x∈A
A relation with all diagonal elements, it can contain any combination of non-diagonal elements.

Eg:
A={1, 2, 3}

So for a relation to be reflexive, it should contain all diagonal elements. In addition to them, we can have possible combination of (n²-n)non-diagonal elements (i.e., 2^n2-n)

Ex:
{(1,1)(2,2)(3,3)} —– ‘0’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)} —– ‘1’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)(1,3)} “
___________ “
___________ “
{(1,1)(2,2)(3,3)(1,2)(1,3)(2,1)(2,3)(3,1)(3,2)} (n²-n) diagonal elements
____________________

Total: 2^n2-n
For the given question n = 5.
The number of reflexive relations = 2^(25-5) = 2²⁰