Counting relations question

Question

I have a small question about relation counting, i'm looking for formulas.

I know that there is a formula for reflexive and anti reflexive.

I'm not sure about the simetric or a-simteric ones, and if we have a formulla for transitive.

Thanks in advance !

Answer 1

The number of $n$-element symmetric relations is $$2^{\binom{n}{2}+n}$$ as answered here. Essentially, for each pair of distinct elements $a$ and $b$ we choose whether or not to include both $(a,b)$ and $(b,a)$, giving $\binom{n}{2}$ binary choices, and for each element $a$ we choose whether or not to include $(a,a)$, giving $n$ binary choices.

For antisymmetric relations, the argument is much the same as the symmetric case, except for distinct pairs $a$ and $b$, we can do one of three things: (a) include $(a,b)$, (b) include $(b,a)$, or (c) include no relation between $a$ and $b$. Thus we get $$3^{\binom{n}{2}}2^n$$ $n$-element antisymmetric relations.

For transitive relations, it's much harder. Wikipedia writes:

No general formula that counts the number of transitive relations on a finite set (sequence A006905 in OEIS) is known.

There is something to say about asymptotics, though; see this MathOverflow question.