How Many Symmetric Relations on a Finite Set? How many symmetric relations are there on an $n$-element set?
Thank you.
 A: This problem is very similar to Number of relations that are both symmetric and reflexive 
A symmetric relation $R$ on a set $A$ is a subset $A\times A$. We can write $R$ as $B\cup C$, where $B$ is a subset of $\{(a,a)\mid a\in A\}$ and $C$ is a subset of $\{(b,c)\in A\times A\mid b\ne c\}$.
Note there are as many choices for $B$ as subsets of $A$, namely $2^n$. 
To count the number of possible sets $C$, we use that $C$ is symmetric, meaning, if $(b,c)\in C$ then also $(c,b)\in C$. Now, let ${}[A]^2$ be the collection of subsets of $A$ of size 2. Note ${}[A]^2$ consists of subsets rather than ordered pairs. Given any $D$ subset of ${}[A]^2$, we can associate to it a set $C$ by setting $C=\{(b,c)\mid \{b,c\}\in D\}$. Note that $C$ is symmetric, since $\{b,c\}=\{c,b\}$.
Conversely, any $C$ symmetric corresponds to a unique $D\subseteq[A]^2$, namely $\{\{b,c\}\mid (b,c)\in C\}$. This is why in $C$ we only allow pairs $(b,c)$ with $b\ne c$, so the resulting $D$ is a subset of ${}[A]^2$ and we have a correspondence.
We have shown that there are as many $C$ as there are subsets $D$ of ${}[A]^2$. But $\displaystyle |[A]^2|={n\choose 2}=\frac{n(n-1)}2$, so the number of subsets is $2^{n\choose 2}$.
Finally, since we can pair any $B$ with any $C$, we have that the number of binary symmetric relations on a set $A$ of size $n$ is precisely $$ 2^{n+{n\choose 2}}=2^{{n+1}\choose 2}.$$ 
A: You can also think of it as a matrix $nxn$, with the elements of the matrix being $(a_i,a_j)$ with $ a_i,a_j \in A$. The elements of the main diagonal can be perfectly chosen for the relation because they are symmetric. For the rest of the elements, picking a pair from the upper triangle say $(a_2,a_1)$ implies that you are also picking $(a_1,a_2)$. So from the total $n^2$ pairs you end up with only $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ from which to choose. You can do this in $2^{\frac{n(n+1)}{2}}$ ways
A: Every relation on a set of N elements can be thought as an NxN matrix.
For a symmetric relation the Matrix is also symmetric.
So, we have $N^2$ elements,distributed as $N$ in Principal Diagonal, and $(N^2-N)/2$ in upper and lower triangles each.
Here we can fill 0/1 in any one of the triangle and the other half will be created after copying the elements (Remember, Symmetric Matrix??).Also the diagonal can be filled with 0/1. 
so we have ${\frac{N^2-N}{2}} + N = {\frac{N^2+N}{2}} $ values with choice 0/1, and remaining are bound to get a single value.
so it is, $2^{\frac{N(N+1)}{2}}$.
A: 
Definition of Symmetry $\forall x,y\in S, xR y\to yRx$

Statement 1 It implies $(x,y)$ and $(y,x)$ must be contained in $R$ concurrently. (Remember there is the case $x=y$)
Assume the cardinality of the set $S$ is $n$, meaning $n$ elements. 
We need to choose 2 elements from $n$ elements, orders considered trivial and $x=y$ is acceptable(See Statement 1).
 That makes the question become the combination with replacement/repetition (meaning the elements chosen can be the same), so we've got the answer:
$$
\text{Total pairs}={n+2-1\choose 2}={n+1\choose 2}\\
\text{Total possible cases}=2^{n+1\choose 2}
$$
(same form as @Andrés E. Caicedo provided)
See this to know more about the combination with replacement/repetition: https://www.mathsisfun.com/combinatorics/combinations-permutations.html
