How many transitive relations on a set of 3 elements $A=\{a,b,c\}$? How many transitive relations on a set of 3 elements $A=\{a,b,c\}$? I know that the number of binary relations on an  n -element set is $2^{n^2}$. In our case, that’s 512. I know that the number of transitive relations should be 171, but how to calculate and prove this? If I check each of the 512 binary relations for transitivity, then it will take months, there should be another way to calculate this, but which one?

I don't think this can be done without a certain amount of drudgery, but you won't have to generate every binary relation.  I'll use the letters $x,y,z$ to represent the elements $a,b,c$, with the understanding that no two of $x,y,z$ are equal.
I would approach this by considering the number of pairs in each relation.  There is $1$ transitive relation with $0$ pairs.  There are $9$ transitive relations with $1$ pair.  The first interesting case is $2$ pairs. There are $36$ such relations.  If one of the pairs is of the form $(x,x)$ then the relation is transitive, so suppose we have a pair $(x,y)$.  The relation will be intransitive if and only if the other pair is one of $(y,x),(y,z),\text{ or }(z,x)$.  There are $6$ choices for $(x,y)$ so we have $\frac{6\cdot3}2=9$ intransitive $2$-pair relations, and $27$ transitive ones.
Try to continue in this manner.  I think that after some point it will get easy, because a transitive relation with some number $n$ of pairs will have to comprise all $9$ pairs, and you can stop.  I doubt $n$ is very close to $9$. Take care to avoid double counting.
EDIT
An alternative is to try to count the number of intransitive relations directly, and subtract from $512$.  For example, a relation that contains $(x,y)$ and $(y,z)$ but not $(x,z)$ is intransitive.  That is, there are $2^6$ intransitive relations that contain $(x,y)$ and $(y,z)$, because the other pairs can be any of the $6$ elements that aren't $(x,z)$.  You'd have to use inclusion-exclusion to avoid double-counting, and my feeling is that it would be quite error-prone.  I think the first approach is probably easier to carry out, though the final solution might be longer.
