0
20kviews
How many symmetric and reflexive relations are there on a set with n elements?
1 Answer
written 8.3 years ago by | modified 8.3 years ago by |
Reflexive Relation : $ 2 ^ {( n^2) −n }$=$2 ^ {n (n−1) } $ The total number of possible relation is $2^{(n^2)}$, out of that the diagonal relation is mandatory so we can opt it out. so the diagonal elements are n.
Symmetric Relation : $2^n $∗ $2 ^ {\frac{n(n−1)} {2} \ }$
we can have all combination of diagonal relation i.e. $2^n$ and upper and lower triangular should be either present or either absent so $2 ^ {\frac{n(n−1)} {2} \ }$ so if we multiply both you will get $2^n $∗ $2 ^ {\frac{n(n−1)} {2} \ }$