How Many Symmetric Relations on a Finite Set?

Question

How many symmetric relations are there on an $n$-element set?

Thank you.

Answer 1

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