Number of symmetric relations on a set with n elements? I cannot figure out why the following method to calculate the number of elements in a set with n elements is wrong:
$N = \text{Total} - \text{not symmetric} = 2^{n^2}- 2^{n(n-1)}$
$n\times(n-1)$ because $n$ choices for a and hence $(n-1)$ choices for b in a non symmetric relation with (a,b).
Can anyone point the flaw in the solution and suggest the right way to do it using complement?

It looks like what you are substracting is not the number of non-symmetric relations, I think you are counting relations thar are totally non-reflexive (I just invented this term). In other words you are counting the relations such that $a\not\sim a$ for every $a$.
The number of relations that are not symmetric is not that easy to count directly I think.
However, we can count the number of symmetric relations. Firstly we must select whether $a\sim a$ for every $a$ and secondly we must decide for each unordered pair $\{a,b\}$ if $a\sim b$ and $b\sim a$ ( remember that one implies the other and vice versa).
Hence there are $n+ \binom{n}{2} = n(n+1)/2$ decisions, and so there are $2^{n(n+1)/2}$ symmetric relations.
