Prove the number of symmetric relation is $2^{\frac{n^2+n}{2}}$

Question

If the number of set $A$ is given. let $n(A)=n$. Prove the number of symmetric relation from $A$ to $A$ is $2^{\frac{n^2+n}{2}}$

We know that number of relations from $A$ to $A$ is $2^{n^2}$

this is obtained by, number of subsets of $A$x$A$ $=2^{n^2}$

every subsets of $A$x$A$ is the relation from $A$ to $A$

like this is any proof is there?

Answer 1

Given two distinct elements $x,y$ in $A$, you can either have both $(x,y)$ and $(y,x)$ in the relation or not. You also can have $(x,x)$ or not. The number of choices you make is the number of unordered pairs from $A$ including pairs of the same member. There are $\frac {n^2+n}2$ of those.

Answer 2

The table of the relation is an $n \times n$ matrix of zeros and ones. If the relation is symmetric, then the part above the diagonal is the same as the part below the diagonal. Each part has $\frac{n^2-n}2$ entries. Therefore, there are $\frac{n^2-n}2+n=\frac{n^2+n}2$ slots to be filled with zero or one, hence $2^\frac {n^2+n}2$ possibilities.