Possible Duplicate:
Number of relations that are both symmetric and reflexive
Let $X$ be a set with $8$ elements.
How many binary relations on $X$ are either reflexive or symmetric or both?
show work. you need not simplify the answer.
Possible Duplicate:
Number of relations that are both symmetric and reflexive
Let $X$ be a set with $8$ elements.
How many binary relations on $X$ are either reflexive or symmetric or both?
show work. you need not simplify the answer.
In a set with 8 elements, a binary relation, $R$ can be thought of as a set of pairs of elements of the set for which that relation is true. That is, $(a,b) \in R \leftrightarrow aRb$ is true. As such, if there are 8 elements, then there 64 possible pairs (order matters). If the relation is reflexive, then this implies that $(a,a) \in R$ for all $a$. So we know that 8 of the pairs must be in the relation. This leaves 56 pairs which can either be in or not be in. So there are $2^{56}$ possible reflexive relations.
Similar combinatorics can be applied to find the answer for symmetric and both.