# Amount of transitive relations on a finite set

In counting the amount of relations on finite sets, we can quite easily count the amount of reflexive and symmetric relations on a finite set. We just consider (in accordance with the definition of a relation on a set as a subset of the cartesian product of the set with itself) a grid with on the vertical axis all the elements of the set and on the horizontal axis all elements of the set. We can then mark the points on the grid which are elements of the relation.

Consider a set $S$ with $|S|=n$ for some $n\in\mathbb{N}$.

The amount of relations on this set is simply $|\mathcal{P}(S^2)|=2^{|S^2|}=2^{n^2}$.

The amount of reflexive relations $S$ can be found by considering that these relations on the grid are all the relations in which in any case the diagonal is in the relation. We see that $n$ pairs are already "chosen", so we can still choose for $n^2-n$ pairs whether or not they are in the relation while keeping the relation reflexive. So there are $2^{n^2-n}$ reflexive relations on $S$.

For the amount of symmetric relations we know that the pairs under the diagonal are in the relation if the corresponding ones above the diagonal are also in the relation. We have the freedom to choose any of the pairs above or on the diagonal of the grid, the amount of which is equal to $T_n=\frac{n(n+1)}{2}$. So there are $2^{\frac{n(n+1)}{2}}$ symmetric relations on $S$.

Relations both symmetric and reflexive are relations for which we can freely choose any pair above the diagonal of the grid. There are $T_{n-1}=\frac{n(n-1)}{2}$ pairs above the diagonal, so there are $2^{\frac{n(n-1)}{2}}$ relations both symmetric and reflexive on $S$.

Now I'm sorry for not getting the point sooner and please correct me if I am wrong about any of them, but I am wondering if there are similar simple expressions for the amount of antisymmetric and transitive relations on this set $S$. I have been told before it is very difficult to visualise transitive relations with the grid I suggested. For antisymmetric relations I think it means the diagonal is definitely in the relation and either a pair above the diagonal is in the relation or the corresponding pair below the diagonal, but not both. I don't really have any ideas as to how I could use these things to come up with a formula for the amount of relations.

Any help and/or comments are appreciated.

Thank you

-
"amount" is used for unindividuated quantities, e.g. "the amount of damage" -- what you mean is "number". –  joriki Nov 24 '12 at 15:48
I only just saw this. I see I have talked about an "amount" in a similar way as well in another question. I will try to be more careful and use "number" from now on. –  user50407 Nov 24 '12 at 20:27

The number of antisymmetric relations is still relatively easy to find. I don't know why you say the diagonal has to be in the relation; the usual definition doesn't require this. Under the usual definition, the diagonal is unconstrained, yielding a factor $2^n$, and each off-diagonal pair has three possibilities, yielding a factor $3^{n(n-1)/2}$, for a total of $2^n3^{n(n-1)/2}$ antisymmetric relations. This is OEIS sequence A083667.