Let $|A| = 8$.
Determine the number of binary relations on $A \times A$ that satisfy the following:
A) Symmetric
B) Neither reflexive or irreflexive
C) Reflexive and symmetric
D) Irreflexive and anti-symmetric
...
I know that a relation $R$ on a set $A$ is reflexive if $(a,a) \in R$ for every element $a \in A$ and that it's symmetric if $(b,a) \in R$ whenever $(a,b) \in R$ for all $a,b \in R$.
This is what I have so far:
Reflexive: $2^{[n(n+1)]/2} = 2^{(8*9)/2} = 2^{36}$
Symmetric: $2^{(n^2 - n)} = 2^{56}$
A) = $2^{56}$
B)$2^{64}$ - $2^{57}$
C) $2^{28}$
D)...?
Any help would be greatly appreciated.
You are correct that part C will be $\;2^{\,p}, \;p = \binom{8}{2} \implies 2^{28}$ relations that are both symmetric and reflexive.
For parts of your question which are not addressed in the related posts:
Hint: For part B, the smart thing would be to compute the total number of relations $\;2^{8^2} = 2^{64}\;$ and subtract (#reflexive + # irreflexive) relations from the total number of relations.
Recall that a relation is irreflexive if and only if for all $x \in A$, $x \not R x$, i.e. $(x, x) \notin R$.
And a relation is antisymmetric if and only if for all $x, y$ in $A$, if $(x, y) \in R$ and $(y, x) \in R$, then $x = y$.