9
$\begingroup$

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

Thank you.

  • 0
    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.2010-12-21
  • 0
    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.2010-12-21
  • 4
    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?2010-12-21
  • 1
    @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?2010-12-21
  • 0
    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.2010-12-21
  • 0
    @Yuval: I did not agree to such a policy. If you like you can restart the thread on meta, but I am being consistent with my statements during the election. @Anonymous: use the multiplication principle again. What does symmetry across the diagonal tell you about which entries are redundant?2010-12-21
  • 0
    @Qiaochu: all the matrices such that the the [ij]!=[ji], where [ij] represent the element on row i column j. If I'm correct, how do I use the multiplication principle here?2010-12-21
  • 0
    @Anonymous: so which entries can you freely fill in such that they determine the rest of the entries?2010-12-21
  • 0
    @Qiaochu: all the matrices such that [ij]=[ji].2010-12-21
  • 0
    Qiaochu: How can I continue from here?2010-12-21

3 Answers 3

9

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

6

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

  • 0
    Andres, please do not provide complete answers to (what I still strongly suspect to be) homework questions.2010-12-21
  • 11
    @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.2010-12-21
  • 0
    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)}.2010-12-21
  • 0
    @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.)2010-12-21
  • 0
    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.2010-12-21
  • 0
    @Anonymous: I think I understood you, and that what you said is not correct. Hence, I gave you the way to fix what you said. You forgot to include the empty set, which is a subset of any set. The subsets of $A$ are $\{\},\{1\},\{2\}\{1,2\}$ and the corresponding $B$ are $\{\},\{(1,1)\},\{(2,2)\},\{(1,1),(2,2)\}$.2010-12-21
  • 0
    @Andres: Sorry, I didn't read correctly what your wrote. Thank you, I'm still reading the proof :)2010-12-21
  • 0
    @Andres: Also, why are there as many choices for B as subsets of A? I know that for each set A with n-elements, the number of A's subsets is 2^n, I just don't see the bijection between B and A. Thanks :)2010-12-22
  • 0
    @Andres: you wrote:"Note that C is symmetric, since {b,c}={c,b}." didn't you mean D?(because C is a set of 2-tuple)2010-12-22
4

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

  • 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](http://math.stackexchange.com/a/694014/120540) that is extremely similar to the one you have in mind.2016-06-21
  • 0
    @shiv-gupta, your answer is definitely clearer than all of the above answers, therefore I voted.2016-08-30
  • 0
    Could you explain more on how you got $2^{\frac{N(N+1)}{2}}$ from ${\frac{N^2+N}{2}}$2017-11-20
  • 0
    @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.2017-11-21