How to find the number of anti-symmetric relations?

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

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.

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$.

Maybe a different way to count the number of antisymmetric relations (I nowhere found this approach, so I post it here). Every relation on $n$ elements could be viewed as a boolean matrix $A = \{(a_{ij})\}_{i,j=1,\ldots, n}$ of size $n \times n$. So we have to count all those boolean matrices that correspond to antisymmetric relations.

First on the diagonal we are free to choose, hence we have $2^n$ possibilities. Now on the non-diagonal entries, consider first the upper right triangular part, i.e. all entries $a_{ij}$ with $i < j$. If for some entry $a_{ij} = 1$, then $a_{ji}$ must be $0$. Otherwise it must be zero itself, but in that case, the other value $a_{ji}$ could be choosen freely.

So we count by first deciding how many $1$'s we have in the upper right triangular part above the diagonal, and then we can freely choose the remaining values in the lower left corner beneath the diagonal which did not correspond to a one, i.e. $a_{ji} \in \{0,1\}$ for $a_{ij} = 0$. Hence we have $$ \sum_{k=0}^{\binom{n}{2}} \binom{\binom{n}{2}}{k} 2^{\binom{n}{2} - k} $$ where the sum is over every matrix after choosing how many ones it will have in the upper right triangular part, which has $\binom{n}{2}$ values in total, $\binom{\binom{n}{2}}{k}$ count the ways we can distribute exactly $k$ ones among these $\binom{n}{k}$ entries, and $2^{\binom{n}{2} - k}$ count the ways we can assign values to the remaining $\binom{n}{2} - k$ entries in the lower left triangular part. So in total we have $$ 2^n \cdot \sum_{k=0}^{\binom{n}{2}} \binom{\binom{n}{2}}{k} 2^{\binom{n}{2} - k} $$ antisymmetric relations, and as $$ 3^{\binom{n}{2}} = (1 + 2)^{\binom{n}{2}} = \sum_{k=0}^{\binom{n}{2}} \binom{\binom{n}{2}}{k} 2^{\binom{n}{2} - k} $$ our solution is consistent with the previous ones.