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?
 A: 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.
A: 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$.
