# Symmetric and reflexive relations on an $n$-element set

So I am to determine the number of both symmetric and reflexive relations on an n-element set. I've read various explanations (yes, Number of relations that are both symmetric and reflexive too) but I still don't quite get it.

If the relations are to be both symmetric and reflexive, why isn't the answer the same as for the reflexive? I mean - when we have some 25-element set, represent it as 5x5 grid, no other points can be symmetric and reflexive at the same time than the diagonal from (1,1) to (5,5). We can choose many symmetric ones apart from those too, but neither will be reflexive.

What do I not understand?

-

Your assumption that the number of (symmetric and reflexive) relations = number of (purely reflexive) relations is wrong.

Let me explain: Say, A= {1,2}

Reflexive relations on A =

{(1,1),(2,2)},

{(1,1),(2,2),(1,2)},

{(1,1),(2,2),(2,1)},

{(1,1),(2,2),(1,2),(2,1)} => Number of reflexive relations = 4 [= 2^(n(n-1)) in general]

But the number of reflexive And symmetric relations = 2^(n(n-1)/2) as is already described in the link you've provided.

The number of reflexive relations is always > The number of reflexive And symmetric.

And in your example,it's not just the principle diagonal. You've neglected the symmetric pairs that can exist along with the ordered pairs necessary to make the relation a reflexive one. i.e {(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1)} is also both reflexive And Symmetric.

-

Reflexive Relation : $2^{(n^2)-n} = 2^{n(n-1)}$ The total number of possible relation is $2^{n^2}$ , out of that the diagonal relation is mandatory so you can opt it out. so the diagonal elements are n.

symmetric Relation : $2^n * 2^{\frac{n(n-1)}{2}}$ you can have all combination of diagonal relation i.e. $2^n$ and upper and lower triangular should be either present or either absent so $2^{\frac{n(n-1)}{2}}$ so if you multiply both you will get $2^n * 2^{\frac{n(n-1)}{2}}$.

-
As you do not use LaTeX, the mathematical symbols in your question are not understood. – Yiorgos S. Smyrlis Jan 27 '14 at 7:45
very true but i was not aware of it !! will do in future ! thanks – JOBBINE JOSEPH Jan 28 '14 at 9:01