Number of relations that are anti-symmetric

Question

Consider set A containing n objects. How many relations of all $2^{n^2}$ on A, are anti-symmetric?

I saw in book that it is $2^n *$ $3^{(n^2 -n)/2}$ but I can't understand why we use 3 as base?

Answer 1

Consider each pair of elements $(a,b)$ where $a$ and $b$ are distinct. Our relation can have one of: $(a,b)$ (as in, $a$ relates to $b$), $(b,a)$ or neither. How many pairs of distinct elements are there? There are $n^2$ total ways to take a pair of elements in $A$, but $n$ of those are of the form $\{a,a\}$ i.e. I pick the same element twice, so I subtract those, giving me $n^2-n$. However, note that this counts both $(a,b)$ and $(b,a)$, but I don't really care about order. Since for each ordered pair, I also have its reverse, so I half my count so I don't double count, giving me $(n^2-n)/2$.

As I said before, you can have either $a$ relates to $b$, $b$ relates to $a$, or neither (having both would defy antisymmetry). In other words, for each of those pairs I counted, I have one of three choices, so I have $3^{(n^2-n)/2}$.

Finally, I still have to consider the possibility that $a$ relates to itself for any element $a$. For each of the $n$ elements, it either relates to itself, or it doesn't, giving me $2^n$. Since picking elements that relate to themselves doesn't affect picking distinct elements that relate to each other, I can do them separately and take the product, giving $2^n * 3^{(n^2-n)/2}$.