Number of transitive relations 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}}$
 A: 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.
A: The problem of finding the number of transitive relations on a set of n elements is non-trivial. The number of relations defined on the set itself grows exponentially ($2^{n^2}$)
For finding the other two, lets consider a matrix form of representing relations (assume rows & columns are ordered by the elements - where a 1 corresponds to existence of an element (ordered pair) & a 0 corresponds to non-existence).
On a set n elements, the matrix is a square matrix with n rows & n columns (where each element corresponds to an ordered pair of elements from the set).
Make the following observations -

All of the diagonal elements correspond to Reflexive Relation.
The mirror elements across the diagonal correspond to Symmetric Relation.
Total no of diagonal elements is $n$
Total no of non-diagonal elements is $n^2 - n$
Total no of mirror-element pairs is $\frac{n^2 - n}{2}$

Now, for a Relation to be Reflexive, all of the diagonal elements must be 1, the other elements may or may not exist (either 0 or 1).
In Symmetric Relations, all of the mirror elements occur in pairs i.e., either both 1 or both 0, the diagonal elements may or may not exist (either o or 1).
Counting this way, its clear that the number of Reflexive relations is $2^{\frac{n^2 - 2}{2}}$ and the number of Symmetric Relations is $(2^n)(2^{\frac{n^2 - n}{2}})$ which is equal to $2^{\frac{n^2 + n}{2}}$
