How Many Symmetric Relations on a Finite Set?

Question

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

Thank you.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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