# Determine the number of binary relations on a set $A = {a_1, a_2, . . . , a_n}$

Determine the number of binary relations on a set $A = {a_1, a_2, . . . , a_n}$ containing for each pair of distinct elements $a_i, a_j$ exactly one of the ordered pairs $(a_i, a_j)$ and $(a_j , a_i)$

-
What have you tried? –  wj32 Oct 30 '12 at 22:20

HINT: Let $m$ be the number of unordered pairs of distinct elements of $A$. For each pair $\{a_i,a_j\}$ you have a two-way choice: put $\langle a_i,a_j\rangle$ into the relation, or put $\langle a_j,a_i\rangle$ into the relation.
1. You’re making a two-way choice $m$ times; in how may ways can you do that?
2. Now, what is $m$? How many unordered pairs of distinct elements of $A$ are there?
Hint: There are $n(n-1)/2$ pairs with $i \lt j$ For each of those, you get to pick exactly one of the pair. There are also $n$ pairs $(a_i,a_i)$, each of which can be in the relation or not.