How many ways to make edges of the graph directed?

Question

Suppose, I have a Complete Undirected Graph with $N$ vertices.

And there is always a choice to make edges of the undirected graph directed ones, so that the whole graph does not have a directed cycle .

---

How many such choices are there to make edges of the graph directed without having a Directed cycle ?

---

I am getting $N!$, But not sure though ?

Answer 1

HINT: Let the vertex set be $[n]=\{1,\ldots,n\}$; you’re asking how many transitive tournaments there are on $[n]$. After you assign a direction to each edge to get a directed graph $G$, you’ve defined a binary relation $R_G$ on $[n]$ by $\langle k,\ell\rangle\in R_G$ if and only if there is an edge from $k$ to $\ell$ in $G$.

• Show that $G$ contains no directed cycle if and only if $R_G$ is a strict linear order on $[n]$.
• How many strict linear orders on $[n]$ are there?