A tournament is called transitive if the fact that there is

A tournament is called transitive if the fact that there is an edge from i to j and an edge from j to k implies the fact that there is an edge from i to k. How many transitive tournaments are there on vertex set [n]?

Solution

Let G be a tournment.

Then G is a directed graph in which every pair of vertices are connected by a single directed edge.

Since G is also transitive G cannot have any cycles.

Because of the above each transitive tournment has atleast one topological order.

Since number of possible topological orders with vertex n is n!, each of n! result in one transitive tournament in G.

So Transitive tournments on vertex set n = n!