How to find the number of anti-symmetric relations?

Question

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?)

Answer 1

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.

Answer 2

HINT: Antisymmetric relations can be counted with an analysis similar to the one used to count symmetric relations. Suppose that we’re building an antisymmetric relation $R$ on $A$. Suppose that $a,b\in A$ with $a\ne b$; $R$ must not contain both $\langle a,b\rangle$ and $\langle b,a\rangle$, but it may contain either of these ordered pairs without the other, and it may contain neither of them. There is no restriction on pairs of the form $\langle a,a\rangle$.

• Thus, for each of the $\binom{n}2$ two-element subsets $\{a,b\}$ of $A$ we have $3$ allowable choices of ordered pairs to put into an antisymmetric relation: we can use $\langle a,b\rangle$ alone, $\langle b,a\rangle$ alone, or neither. In how many ways can we choose which ordered pairs of non-identical elements are to belong to $R$?

• In addition we may keep any subset of the $n$ pairs of the form $\langle a,a\rangle$. In how many ways can we choose which pairs of the form $\langle a,a\rangle$ are to belong to $R$?

Now combine those two numbers properly to get the number of antisymmetric relations on $A$.