# How Many Symmetric Relations on a Finite Set?

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

Thank you.

-
When you say relation, do you mean it has to include all the $n$ elements in it, or is the empty relation (for example) is also counted - as it satisfies symmetry. – Asaf Karagila Dec 21 '10 at 21:11
all the Symmetric relations, including the empty relation. For instance, A={1,2} then the symmetric relations are: empty set, {(1,1)},{(1,2),(2,1)} etc. – Anonymous Dec 21 '10 at 21:23
This has a homework feel to it - is it? Since I don't just want to give the answer, here's a good hint: how many total relations are there for an n-element set, and what do they correspond to? Now, what do the symmetric relations correspond to, and can you use that to find your answer? – Steven Stadnicki Dec 21 '10 at 21:46
@Qiaochu I thought we agreed that if the OP doesn't say it's homework then we can't assume it is. In the past people have been flamed for asking what Steven is asking above. Do we have a new policy on, now that the elections are over? – Yuval Filmus Dec 21 '10 at 21:51
Steven, the number of all relations could be seen as the number of all the matrices of nxn, where every entry in the matrix could be either 0 or 1 - therefore, by the multiplication principle there is a total of 2^(n^2). From here, I don't see how to find the number of all the symmetric relations - I just know that it has to be symmetric from the diagonal or on the diagonal. – Anonymous Dec 21 '10 at 21:59

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

-
Andres, please do not provide complete answers to (what I still strongly suspect to be) homework questions. – Qiaochu Yuan Dec 21 '10 at 22:18
@Qiaochu: There is no indication to me that this is a homework problem. I expect people to act honorably, and be honest. If the OP does not explicitly say this is a homework problem, and it is not self-evident to me, I won't assume otherwise. – Andrés Caicedo Dec 21 '10 at 22:24
Hello Andres, thank you for the detailed proof, I haven't finished reading it. if A={1,2} then the number of set B we have isn't 4 but 3, if we count the subsets as sets. ({(1,1)},{(2,2)},{(1,1),(2,2)}. the fourth set is {(2,2),(1,1)} but this set is equal to {(1,1),(2,2)}. – Anonymous Dec 21 '10 at 22:25
@Anonymous: I think you are not counting the empty relation $\{\}$. It is symmetric (so you have 4 rather than 3 after all), but I am not sure whether you have some convention that excludes it. (I don't think you want to exclude it, according to the comments above.) – Andrés Caicedo Dec 21 '10 at 22:29
Andres: I think you didn't understand me. You wrote: "Note there are as many choices for B as subsets of A, namely 2^n". I think that your definition of B is not correct, so I gave an example of A={1,2} and then I wrote the sets B by your definition. – Anonymous Dec 21 '10 at 22:33

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

-