Number of transitive relations

Question

We have a set $A$ with cardinality $n$. How to find the number of transitive relations on $A$?

Also how do we get the following results?

Number of reflexive relations on $A=2^{n^2-n}$

Number of symmetric relations on $A=2^{\frac{n(n+1)}{2}}$

Answer 1

We can think of binary relations as something like an ordered pair mapped to $\{0,1\}$. So, to fully characterize a binary relation, we just need to determine whether a certain pair $(a,b)$ is mapped to $0$ or $1$. That is why the number of all binary relations on set $A$ with cardinality $n$ is $2^{n^2}$. We first have $n^2$ ordered pairs, then there are $2^{n^2}$ mappings.

Following this thought, we can actually find the number of non-reflexive relations. There are $n$ pairs in form $(a,a)$, so there are only $n^2 - n$ pairs with distinct two elements. Those are the pairs we have to consider, resulting in $2^{n^2 - n}$ reflexive relations.

For the symmetric relations, consider it this way. Once we have determined $(a,b)$, we have determined $(b,a)$ as well. So we only need to work on $\frac{n^2 - n}{2}$ pairs. But hold on, we are forgetting $n$ pairs in form $(a,a)$. So we need to work on $\frac{n^2 - n}{2} + n = \frac{n(n+1)}{2}$ pairs, resulting in $2^{\frac{n(n+1)}{2}}$ relations.

I haven't thought of a clever way of computing number of transitive relations yet but I hope this help.