GATE CSE 2010 | Question: 3

Question

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

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

Comments

1) total number of elements=$n^2$

2) total diagonal elements = $n$.

3) total number of non-diagonal elements=$n^2-n=n(n-1)$.

4) In reflexive relations diagonal elements are mandatory and non-diagonal elements are not mandatory.

So total number of relfexive relations =$2^{n(n-1)}\implies 2^{5.4}=2^{20}$.

---

A lot of variations of this question is beautifully explained in this $\href{https://www.youtube.com/watch?v=Z9khyLCt2-I&list=PLIPZ2_p3RNHjHnhdkPWFAlcizVQJ8w4TX&index=15}{video}$ by Deepak sir.

---

Type	Count	Reasoning
All relations	2^(n²)	every cell free
Reflexive	2^(n²−n)	diagonal forced on
Irreflexive	2^(n²−n)	diagonal forced off
Symmetric	2^(n(n+1)/2)	diagonal free + one choice per unordered pair
Anti-symmetric	2ⁿ · 3^(n(n−1)/2)	each off-diagonal pair has 3 states
Reflexive + symmetric	2^(n(n−1)/2)	diagonal forced, pairs free
Equivalence	Bₙ	count partitions

Answer 1

A relation consists of set of ordered pairs $(a,b)$. Here, $a$ can be chosen in $n$ ways and similarly, $b$ can be chosen in $n$ ways. So, totally $n^2$ possible ordered pairs are possible for a relation. Now each of these ordered pair can either be present in the relation or not- 2 possibilities for each of the $n^2$ pair. So, total number of possible relations =  $$2^{\left(n^2\right)}$$

Now, for a relation $R$ to be reflexive, ordered pairs $\left\{(a,a) \mid a \in S \right\}$, must be present in $R$. i.e.; the relation set $R$ must have $n$ ordered pairs fixed. So, number of ordered pairs possible is $ n^2 - n$ and hence total number of reflexive relations is equal to $$ 2^{\left(n^2-n\right)}$$

for $n=5$, answer will be, $2^{5^2-5}=2^{20}$

Therefore, option C is correct

Comments

Beautifully explained sir.

---

@Arjun sir , why we are doing (n*n – n)

Answer 2

The number of reflexive relations =2^(n^2 - n) so option c is correct

Answer 3

The number of reflexive relations is given by $2^{n^{2}-n}$. The reasoning is not always very clear so here is the explanation:

• If the relation must be reflexive means we need to have all the self-pairs, e.g. (1,1) for all elements in the set. So choice for these is one as they have to be included, no matter what.
• Now come the other pairs left. These may or may not be included and it will not affect the overall reflexivity of the relation, as all self-pairs are already selected.

So, total self-pairs = $n$, and remaining pairs = ${n^2}-n$ , which is total minus the self-pairs and the left pairs still have a choice.

Hence total number of reflexive pairs =  $2^{n^{2}-n}$

Substituting $n$=5 for this question we get $2^{20}$, which is option (C).

 

Answer 4

A relation consists of set of ordered pairs (a,b).

possible number of reflexive relations on a set of n elements=

2^(n^2 - n)

here n=5 

so answer is , 2^(5^2 - 5) =20

Answer 5

we know n^2 ordered pairs are possible. Think like this if we want a relation and a condition according to question is that it must have reflexive pairs in it. Now in every relation which have to be reflexive there will always be n ordered pairs which are fixed ,, we can't do anything about it, now we are left with how many pairs ? ans. n^2 - n , from here we again have 2 possibilities for every ordered pair you either take it or don't take it. so, 2x2x2x2 ........  (n^2-n) times that equals to 2^(n^2-n).

 

If i am wrong please correct:).

Answer 6

1) We can fix the mandatory pairs as $\{(a,a), (b,b), (c,c), (d,d), (e,e)\}$. let's call it parent set since they will be present in all relations.
2) We can add any set (a,b) (b,a) etc. to the parent set and it will remain reflexive
3) Such amount of pairs will be $2 \times \binom{5}{2} = 20$. Multiplying by 2 so that we get both (a,b) & (b,a).
4) Then each pair has 2 independent choices (Include or Exclude) in parent set:

$$\text{Total Reflexive Relations} = 2^{20}$$