[Math] How to find the number of anti-symmetric relations

combinatoricselementary-set-theoryrelations

I know that given a set $A = \{1, 2, 3, … , n\}$, the total number of relations on $A$ is $$2^{n^2}$$ The number of reflexive relations is $$2^{n^2 – n}$$ The number of symmetric relations is $$2^{{n+1}\choose 2}$$ But how can I find the number of anti-symmetric relations? With a small set, say $n = 4$, it can be easy to just brute force it. Is there another way (perhaps using the inclusion-exclusion principle?)

Best Answer

I take the definition of an antisymmetric relation $R$ to mean that $a R b$ and $b R a$ implies $a = b$, but for a given $a$ and $b$ it might well be that neither $a R b$ nor $b R a$.

So the number should be $$ 2^{n} 3^{\binom{n}{2}}, $$ because you have two choices for pairs $(a, a)$ (either $a R a$ or not) while for pairs $(a, b)$, with $a < b$, you have three mutually exclusive choices, either $a R b$ or $b R a$ or neither.