Number of acyclic orientations
Task number: 4458
Count how many acyclic orientations the complete graph on \(n\) vertices has.
Solution
Let the vertices of the graph be numbered from 1 to \(n\). We construct a bijection between the permutations on the set \({1,\ldots,n}\) and the acyclic orientations of the graph.
Each acyclic orientation can be topologically ordered, yielding a permutation of vertices. Since every two vertices are connected by an edge, the topological ordering is uniquely determined.
Each permutation \(\pi\) determines an orientation: for a pair of vertices \({i,j}\), we look at what position they lie in the permutation, and orient the edge from the smaller position to the larger one.
Answer
There are \(n!\) acyclic orientations of the complete graph \(K_n\).
