Total Number of Reflexive Relations on a Finite Set Having n Elements

The Total Number of Reflexive Relations on a Finite Set Having n Elements is

Question

The total number of reflexive relations on a finite set having \( n \) elements is ……………………….

Solution

Let a finite set \( A \) have \( n \) elements.

Then the Cartesian product \( A \times A \) contains:

\[ n^2 \]

ordered pairs.

A relation on \( A \) is reflexive if:

\[ (a,a)\in R \quad \text{for all } a\in A \]

Thus, all diagonal elements:

\[ (a_1,a_1), (a_2,a_2), \ldots, (a_n,a_n) \]

must necessarily be included in the relation.

So, out of the \( n^2 \) ordered pairs:

  • \( n \) pairs are fixed (must be included)
  • Remaining \( n^2-n \) pairs may or may not be included

Hence, the total number of reflexive relations is:

\[ 2^{\,n^2-n} \]

Therefore, the required answer is:

\[ \boxed{2^{n^2-n}} \]

Next Question / Full Exercise

Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *