Asymmetric relation on finite set

Question

The set $X$ has $n$ elements. A relation $R$ on $X$ is asymmetric if $(x,y) \in R \to (y,x) \notin R$ for all $x$ and $y \in X$. Determine how many asymmetric relations $R$ there are in $X$, for example, by first answering the following questions where it is assumed that $X = \{ {x_1},{x_2}, \ldots ,{x_n}\} $:

1. Does $({x_i},{x_i}) \in R$ or $({x_i},{x_i}) \notin R$ hold if $R$ is asymmetric?
2. How many alternatives are there when one considers whether the pairs $({x_i},{x_j})$ and/or $({x_j},{x_i})$ belong to the relation $R$ if $1 \leq i < j \leq n$ and $R$ is asymmetric?
3. How many pairs of integers $(i,j)$ are there so that $1 \leq i < j \leq n$?
4. Calculate the number of asymmetric relations using the results from parts (a), (b), and (c) together with the product principle.

My attempt:

1. Only $({x_i},{x_i}) \notin R$ will hold, because if we have ${x_i}R{x_i}$ the asymmetric condition is not satisfied.

2. $n - 1$

3. $(n-1)!$

4. $(n-1)!$

Answer 1

1) Assuming $xRx$ where $R$ is asymmetric we find $\neg xRx$. But $xRx\wedge \neg xRx$ cannot be true, so we conclude that the assumption is wrong. Final conclusion: $\neg xRx$.

2) For $i,j\in\{1,\dots,n\}$ with $i<j$ there are $3$ alternatives:

• $\neg x_i R x_j$ and $\neg x_j R x_i$
• $x_iRx_j$ and $\neg x_j R x_i$
• $\neg x_i R x_j$ and $x_j R x_i$

3) There are $\binom{n}2$ ways to choose two distinct integers from $\{1,\dots,n\}$.

4) There are $3^\binom{n}2$ distinct asymmetric relations on $X=\{x_1,\dots,x_n\}$.