NIELIT 2016 DEC Scientist B (IT) - Section B: 28

Question

What is the possible number of reflexive relation on a set of $5$ elements?

• A. $2^{10}$
• B. $2^{15}$
• C. $2^{20}$
• D. $2^{25}$

Answer 1

Similar question: https://gateoverflow.in/333214/gate2020-cs-17

So, the total number of relations over a set of  $n$  elements is:  $2^{n^{2}}$

No. of elements excluding the diagonal elements:  $n^{2}-n$

These elements can either be chosen or not chosen. (we have to chose diagonal elements.So only 1 way to chose them all)

So, the total number of reflexive relations possible over a set of  $n$  elements is:  $2\times2\times....(n^{2}-n)times$  $=$   $2^{n^{2}-n}$

For this question,  $n=5$  $\Rightarrow$  answer is :  $2^{25-5}=2^{20}$

Option C is correct.

Answer 2

………………………………………….