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)$
Determine the number of binary relations on a set $A = {a_1, a_2, . . . , a_n}$
-1
$\begingroup$
combinatorics
discrete-mathematics
2 Answers
2
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.
- You’re making a two-way choice $m$ times; in how may ways can you do that?
- Now, what is $m$? How many unordered pairs of distinct elements of $A$ are there?
1
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.