# How Many Symmetric Relations on a Finite Set?

How many symmetric relations are there on 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. Commented Dec 21, 2010 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. Commented Dec 21, 2010 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? Commented Dec 21, 2010 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? Commented Dec 21, 2010 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. Commented Dec 21, 2010 at 21:59

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

• This is a perfectly fine way to count, but in the future, it may be better to not answer four year old questions, if there is an answer that is extremely similar to the one you have in mind. Commented Jun 21, 2016 at 20:12
• @shiv-gupta, your answer is definitely clearer than all of the above answers, therefore I voted. Commented Aug 30, 2016 at 6:32
• Could you explain more on how you got $2^{\frac{N(N+1)}{2}}$ from ${\frac{N^2+N}{2}}$ Commented Nov 20, 2017 at 0:36
• @Rionic in each box you have 2 choices, either 1 or 0. Think of number of different binary numbers of ${\frac{N^2+N}{2}}$ bits. Start with 1 bit, you can have 2 numbers 0 and 1. For 2 bits you can have 4 namely, 00, 01, 10, and 11. Work it out. Commented Nov 21, 2017 at 8:08

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

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. Commented Dec 21, 2010 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. Commented Dec 21, 2010 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)}. Commented Dec 21, 2010 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.) Commented Dec 21, 2010 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. Commented Dec 21, 2010 at 22:33

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