Counting number of relations that are symmetric and reflexive.

Question

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors logic I am a bit confused when it comes to combinatorics.

So for a finite set, he says that let $n = |A|$ $n$ is also the number of reflexive ordered pairs. I understand this part. So next since we are crossing the set $|A x A|$ = $n^2$ which is the number of total ordered pairs from the cross.

So where I am getting a bit lost is he says that there are $2^{n^2-n}$ relations that are both reflexive and symmetric. So I hope I am understanding this part right. But is that because if we have all ordered pairs, and we want to include them or not include them then thats 2 choices so we have $2$ well we have $n^2$ pairs, and we don't want to include the reflexive pairs in our choice so we must subtract them which is why we have $2^{n^2-n}$

So later he proves that for the # of relations that are both reflexive/symmetric we have $(2^n)(2^{\frac{n^2-n}2})$ Here I am loss,why are we giving the reflexive pairs a choice if we are trying to find # of relations that are both reflexive/symmetric then wont not including one mean that relation is not reflexive? and is the above expression equivalent to $(2^{\frac{n^2+n}2})$

Answer 1

$(2^n)(2^{\frac{n(n-1)}{2}})=2^{\frac{n(n+1)}{2}}$ (exponents add when you multiply) is the number of symmetric relations that are not necessarily reflexive. The $2^n$ factor disappears when we impose reflexivity because it counts the number of ways to choose a set of pairs of the form $(a,a)$, of which there are $n$.

Answer 2

Here's another way to think of it:

A relation on a set $\{a_1,\dots,a_n\}$ can be represented by an $n\times n$ matrix of $0$s and $1$s, with a $1$ in the $ij$ position if $a_i$ is related to $a_j$.

For a symmetric and reflexive relation, we can choose the entries above the main diagonal freely, and then this will determine the entries below the diagonal (due to the symmetry requirement). All the main diagonal entries must be $1$ (due to reflexivity).

There are $\frac{n^2-n}{2}$ entries above the diagonal, and so the result follows.