Given set A has n elements. Find
1) Number of all reflexive relations?
2) Number of all symmetric relations?
3) Number of all reflexive and symmetric relations? Why is enumeration of transitive relations difficult?
1) Relation could be viewed as a digraph hence after the self loop edge for each vertices. There are ${n \choose 2}$ edges hence two choices for each i.e either a relation or not Hence answer:$ 2 ^ {n \choose 2} $
2) Here another choice of self loop. There are ${n \choose 2}$ + 1 edges hence two choices for each i.e either a relation or not Hence answer:$ 2 ^ {{n \choose 2}+1} $
Is this correct? Third one I am very confused how to approach.
1) When it comes to combinations, order doesn't matter, but in this case, the order of the two vertices picked does matter since we are working with a digraph. So instead of ${n \choose 2}$ possible edges, we have $2 { n \choose 2}$ possible edges and hence there are a total of $2^{2 {n \choose 2}}$ reflexive relations.
2) Since we are working with symmetric relations, now we can use ${n \choose 2}$ instead of $2{n \choose 2}$. For the self-loop, we don't have just one self-loop, we have $n$ self-loops each of which we have the choice of having or not. So we have a total of $2^{{n \choose 2}+n}$ symmetric relations.
3) This is the same as 2 except now we don't have to make any choices about self-loops so the answer is simply $2^{{n \choose 2}}$