How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it?

For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but how to find only the transitive relations? Is there a formula for finding this or is it a counting problem?

Also how to find this for any number of elements $n$?

Solution 1:

There is no simple formula for this number (but see http://oeis.org/A006905 for the values for small $n$). The case $n=2$ is small enough that you can list out all 16 different relations and count the ones that are transitive. (You should get 13 of them.)

Solution 2:

Although there's no formula, results for small $n$ can be obtained by recursion. This paper proves that, if there are $T_n$ transitive relations and $P_n$ partial orders on an $n$-element set, and if we define $N_k\left( n\right):=\sum_{s=0}^k\binom{n}{s}S\left( n-s,\,k-s\right)$ where $S\left( n,\,k\right):=\frac{1}{k!}\sum_{i=1}^k\left( -1\right)^{k-i}\binom{n}{k}i^n$, then $T_n=\sum_{k=1}^n N_k\left( n\right)P_k$. Unfortunately, $P_n$ is also only known for small $n$; we can't obtain further $P_n$ with any known recursion, which in turn caps computing $T_n$.