# Total no. of reflexive relations on a set of n elements

• Dec 27th 2011, 09:01 PM
nikhilbhr
Total no. of reflexive relations on a set of n elements
The number of reflexive relations on an n-element set is 2n2−n
Can anybody tell me why so?

• Dec 27th 2011, 09:52 PM
FernandoRevilla
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by nikhilbhr
The number of reflexive relations on an n-element set is 2n2−n Can anybody tell me why so?

Hint Every relation $\displaystyle R$ on $\displaystyle A=\{a_1,\ldots,a_n\}$ is an element of $\displaystyle \mathcal{P}( A\times A)$ . So, we have $\displaystyle \textrm{card}\;\mathcal{P}( A\times A)=2^{\;\textrm{card }\mathcal{P}( A\times A)}}=2^{n^2}$ relations on $\displaystyle A$ . Could you continue?
• Dec 28th 2011, 03:19 AM
Plato
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by nikhilbhr
The number of reflexive relations on an n-element set is $\displaystyle 2^{n^2-n}$ Can anybody tell me why so?[/I]

Here is a different approach.
Any reflexive relation on a set of n elements must contain the diagonal. The diagonal has n elements.
So how many off-diagonal elements are there?
Now look at your answer, $\displaystyle 2^{n^2-n}$.
How are they related?
• Dec 28th 2011, 03:27 AM
nikhilbhr
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by Plato
Here is a different approach.
Any reflexive relation on a set of n elements must contain the diagonal. The diagonal has n elements.
So how many off-diagonal elements are there?
Now look at your answer, $\displaystyle 2^{n^2-n}$.
How are they related?

I understood your approach but can u tell me how you are correlating off-diagonal elements with reflexive relation.
• Dec 28th 2011, 03:43 AM
Plato
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by nikhilbhr
I understood your approach but can u tell me how you are correlating off-diagonal elements with reflexive relation.

How many subsets of off-diagonal elements are there?
• Dec 28th 2011, 05:35 PM
nikhilbhr
Re: Total no. of reflexive relations on a set of n elements
total elements in that matrix=nXn
total diagonal element=n
so obviously power set off-diagonal elements=2^(n^2-1).
But i have problem with the approach u are using .Can please how off-diagonal elements are correlated with reflexive relation..
Thanx for help.
• Dec 29th 2011, 12:03 AM
FernandoRevilla
Re: Total no. of reflexive relations on a set of n elements
Denote $\displaystyle \Delta$ the diagonal of $\displaystyle A\times A$ with $\displaystyle A=\{a_1,\ldots,a_n\}$ . Every reflexive relation $\displaystyle R$ on $\displaystyle A$ has the form $\displaystyle R=\Delta\cup B$ with $\displaystyle B\subset A\times A-\Delta$ . But $\displaystyle A\times A-\Delta$ has $\displaystyle n^2-n$ elements, so there are $\displaystyle 2^{n^2-n}$ reflexive relations on $\displaystyle A$ .
• Dec 29th 2011, 01:24 AM
nikhilbhr
Re: Total no. of reflexive relations on a set of n elements
Thank u very much for your valuable help..Now i got where was the problem.Actually R= (set of diagonal element) U B ,i havent thought of this expression