finding number of unique outcomes of round-robin tournament with cycle
A round robin tournament is a tournament where each player plays other
player once and there is no draw. If a team wins against all other then it
is called Total Winner. Similarly we define Total Looser as a team which
looses all matches.
EDITED::
Let us define order by win/loss. If $A$ wins $B$ and $B$ wins $C$ then it
is ordered as $\dots >A>B>C>\dots$
Consider $n\ge 3 $ teams, $\frac{n(n-1)}{2}$ games are played and
$2^{\frac{n(n-1)}{2}}$ unique results might be possible. Out of those
$2^{\frac{n(n-1)}{2}}$ possible results, how many unique outcomes are
there such that we can order every player (only once) such that it forms a
cycle. i.e. $$P_1 > P_2 > P_2 > \dots > P_n > P_1$$
Some of my thoughts:: There cannot be cycle if there is Total Winner or
Total Looser. I found (by using Principle of Inclusion Exclusion) out
there exists
$$2^{\frac{n(n-1)}{2}}-(2n)2^{\frac{(n-1)(n-2)}{2}}+n(n-1)2^{\frac{(n-3)(n-2)}{2}}$$
possible results of the tournament where there is no Total Winner or no
Total looser.
ADDED:: I wrote a short script for total matches outcomes and outcomes
with no total winner or looser. But couldn't write more to detect cycles.
For $n=3$ & $n=4$, all matches where there is no total winner or total
looser have some sort of cycles.
ADDED::
Here is updated code. If three players played game, player $(1), (2)$, and
$(3)$ the outcomes are
[(1, 2), (1, 3), (2, 3)] $ \leftarrow (1)$ is total winner so there can't
be cycle.
[(1, 2), (1, 3), (3, 2)]
[(1, 2), (3, 1), (2, 3)]
[(1, 2), (3, 1), (3, 2)]
[(2, 1), (1, 3), (2, 3)]
[(2, 1), (1, 3), (3, 2)]
[(2, 1), (3, 1), (2, 3)]
[(2, 1), (3, 1), (3, 2)]
Here, $(1,2)$ means match was played by $(1)$ and $(2)$ and $(1)$ won the
game.
The following forms a cycle (also it is the only outcome where there are
no total winner and total looser)
[(1, 2), (3, 1), (2, 3)] $ \implies 1>2>3>1$
[(2, 1), (1, 3), (3, 2)] $\implies 1>3>2>1$
Thanks you in advance.
No comments:
Post a Comment