Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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,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.

share|cite|improve this answer

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}}$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.