The number of reflexive relations on ann-element set is 2n2−n

Can anybody tell me why so?

Printable View

- Dec 27th 2011, 09:01 PMnikhilbhrTotal no. of reflexive relations on a set of n elements
The number of reflexive relations on an

*n*-element set is 2*n*2−*n*

**Can anybody tell me why so?**

- Dec 27th 2011, 09:52 PMFernandoRevillaRe: Total no. of reflexive relations on a set of n elements
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?__Hint__ - Dec 28th 2011, 03:19 AMPlatoRe: Total no. of reflexive relations on a set of n elements
- Dec 28th 2011, 03:27 AMnikhilbhrRe: Total no. of reflexive relations on a set of n elements
- Dec 28th 2011, 03:43 AMPlatoRe: Total no. of reflexive relations on a set of n elements
- Dec 28th 2011, 05:35 PMnikhilbhrRe: 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 AMFernandoRevillaRe: 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 AMnikhilbhrRe: 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