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 would think about it like this:
A preorder is a transitive and reflexive relation. Given any transitive relation $R$ on a set $X$, if we define a new relation $R'$ by $R' = R\cup \{(x,x)\mid x\in X\}$, then $R'$ is a preorder. Let's call $R'$ the "reflexivization" of $R$. Note that if $R$ is already a preorder, then $R' = R$.
The "reflexivization" operation gives a surjective function from the set of all transitive relations on $X$ to the set of all preorders on $X$. So if we want to count all the transitive relations on $X$, we can count the preorders on $X$ and then count, for each preorder $\leq$, how many transitive relations $R$ have $R' = {\leq}$.
Why are preorders easier to count than transitive relations? Well, for one thing they're easier to picture. Also, counting preorders reduces further to counting partitions and partial orders.
Given a preorder $\leq$ on a set $X$, there is an associated equivalence relation $\sim$ given by $x\sim y$ iff $x\leq y$ and $y\leq x$. Then the preorder $\leq$ is uniquely determined by the induced partial order on the quotient $X/{\sim}$. (A partial order is a preorder such that if $x\leq y$ and $y\leq x$, then $x = y$.)
So specifying a preorder on $X$ is the same as deciding on a partition of $X$ into equivalence classes and then deciding on a partial order on these classes.
Ok, so we count partitions of $X$, and then count partial orders on the quotients, and then count preimages of the resulting preorders under the reflexivization map. For the last step, suppose $R' = {\leq}$ and $R$ is transitive. If a $\sim$-class $C$ has more than one element, say $x,y\in C$, then $x\leq y$ and $y\leq x$ implies $xRy$ and $yRx$, so by transitivity, $xRx$ and $yRy$. So $R$ can only differ from $\leq$ by dropping reflexivity on elements that are in singleton $\sim$-classes. For each singleton $\sim$-class, we can choose to drop reflexivity or not, independently, while maintaining transitivity. It follows that the preimage of $\leq$ under the reflexivization map has size $2^n$, where $n$ is the number of singleton $\sim$-classes for $\leq$.
We're finally ready to count the transitive relations on $A = \{a,b,c\}$.
If there is just one class $\{a,b,c\}$, then there is a unique partial order on the quotient, giving rise to $1$ preorder, and hence to $1$ transitive relation  (since there are no singleton classes).
If there are two classes, say $C$ and $C'$, then there are three partial orders on the quotient: $C \leq C'$, or $C'\leq C$, or the two classes are incomparable. Since there are three ways to partition $A$ into two classes, and each way gives three partial orders, there are $9$ such preorders. Each of these preorders has just one singleton class, so we have $9\cdot 2^1 = 18$ transitive relations.
Finally, if there are three classes, say $C_1$, $C_2$, and $C_3$, then there are $19$ partial orders, giving rise to $19$ preorders (since there is a unique way to partition $A$ into three classes) and hence, since there are three singleton classes, to $19\cdot 2^3 = 152$ transitive relations. How do we get to $19$ partial orderss? There is $1$ discrete partial order (none of the classes are comparable), $6$ partial orders in which one element is incomparable to the other two (and the other two are comparable), $3$ in which one element is below the other two (and the other two are incomparable), $3$ in which one element is above the other two (and the other two are incomparable), and $6$ linear orders.
In total, there are $1 + 18 + 152 = 171$ transitive relations on $A$.
