A simple connected digraph in which there is exactly one dir

A simple, connected digraph in which there is exactly one directed edge between every pair of vertices is called a tournament digraph.

How many possible outcomes are there in a boxing match among n boxers, where there is no draw and every boxer wins at least one match and loses at least one match?

Solution

Lets Write X for set of all possible outcomes of n boxer tournament with no tis. Since there are (n 2) individual matches, the cardinality of X is given by |X| = 2^(n*(n-1))/2.
We next count the set A of outcomes where some boxer wins all his matches; first decide which boxer it will be and then decide how matches not involving this particular boxer will be 2^((n-1)(n-2))/2. Thus |A| = n*2^((n-1)(n-2))/2.
The set B of tournament in which some player looses all his matches has same cardinality. Finally we count intersection of A and B, first pick overall winner then overall loser.
By inclusion exclusion principle,
|X| - |A| - |B| + |A int. B| = 2^(n*(n-1))/2 - 2n*2^((n-1)(n-2))/2 + n(n-1)*2^((n-1)(n-2))/2

When n=3, this yields 2 outcomes. Labeling a,b,c. This in round robin tournament involving 3 player without a big winner or a big loser, there is always three cycle involving the players.