The number of symmetric relations defined on the set [1,2,3,4] which are not reflexive is …

Question

The number of symmetric relations defined on the set $$\{1,2,3,4\}$$ which are not reflexive is \_\_\_\_\_\_\_\_\_.

Answer: 960

Accepted Answer

To find the number of symmetric relations on the set ${1,2,3,4}$ that are not reflexive, we first calculate the total number of symmetric relations and then subtract the count of those that are both symmetric and reflexive.
A symmetric relation involves pairs where if a pair (x, y) is in the relation, then (y, x) is also in the relation. For a set with $n$ elements, there are $\frac{n(n+1)}{2}$ slots in the relation matrix that can independently be occupied or not, corresponding to a total of ${2}^{\frac{n(n+1)}{2}}$ possible symmetric relations.
A relation is reflexive if every element is related to itself, requiring all diagonal slots of the relation matrix (n of them) to be filled. The remaining $\frac{n(n-1)}{2}$ slots can be filled in any manner, leading to ${2}^{\frac{n(n-1)}{2}}$ reflexive (and possibly symmetric) relations.
For the set ${1,2,3,4}$ ($n=4$):
Total symmetric relations: ${2}^{\frac{4(4+1)}{2}}={2}^{10}=1024$Symmetric and reflexive relations: ${2}^{\frac{4(4-1)}{2}}={2}^{6}=64$Therefore, the number of symmetric relations that are not reflexive: $1024-64=960$.

Solutions · 1