How many transitive relations on a set of 3 elements $A=\{a,b,c\}$?

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.

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$.