7
$\begingroup$

How many arrangements are possible for a round robin tournament over an even number of players $n$?

A round robin tournament is a competition where $n = 2k$ players play each other once in a heads-up match (like the group stage of a FIFA World Cup). To accommodate this, there are $n-1$ rounds with $\frac{n}{2}$ games in each round. For an arrangement of a tournament, let's say that the matches within an individual round are unordered, but the rounds in the tournament are ordered. For $n$ players, how many possible arrangements of the tournament can there be?

...

I don't know if a formal statement is needed, but hey ...

Let $P = \{ p_1, \ldots, p_n \}$ be a set of an even $n$ players. Let $R$ denote a round consisting of a set of pairs $(p_i,p_j)$ (denoting a match), such that $0<i<j\leq n$, and such that each player in $P$ is mentioned precisely once in $R$. Let $T$ be a tournament consisting of a tuple of $n-1$ valid rounds $(R_1, \ldots, R_{n-1})$, such that all rounds in $T$ are pair-wise disjoint (no round shares a match).

How many valid constructions of $T$ are there for $n$ input players?

The answer for 2 players is trivially 1. The answer for 4 players is 6. I believe the answer for 6 players to be 320. But how can this be solved in the general case?

$\endgroup$
3
  • $\begingroup$ You can arrange matches with no overlap by arbitrarily numbering the teams $0 - (n - 1)$, then in round $i$ match teams such that the sum of ther numbers is $i$ mod $n$. You can relabel the teams in $(n-1)!$ ways and do the above, so i think this is the answer.., $\endgroup$
    – gnometorule
    Jan 22, 2013 at 18:25
  • $\begingroup$ Interesting ... but is this the only way to derive valid configurations? (That also means I miscounted in the 6 player case ... if $(n-1)!$ the answer would be 120 rather than 320.) $\endgroup$
    – badroit
    Jan 22, 2013 at 18:27
  • 1
    $\begingroup$ MatchIng using mod is a standard example when introducing mod, but not necessarily the only way of doing this. I'm also only kinda sure this is right, but it's definitely close. I'm reading these questions often on breaks on my iPhone so it's what came to my mind. :) $\endgroup$
    – gnometorule
    Jan 22, 2013 at 18:31

1 Answer 1

Reset to default
6
+50
$\begingroup$

This is almost the definition of a "$1$-factorization of $K_{2k}$", except that a $1$-factorization has an unordered set of matchings instead of a sequence of rounds. Since there are $2k-1$ rounds, this means that there are $(2k-1)!$ times as many tournaments, according to the definition above, as there are $1$-factorizations.

Counting $1$-factorizations of $K_{2k}$ seems to be a nontrival problem; see the Encyclopedia of Mathematics entry. The number of $1$-factorizations of $K_{2k}$ is OEIS sequence A000438. Also, see this paper (also here) for a count in the $k=7$ case.

$\endgroup$
1
  • $\begingroup$ Perfect, thanks! I can follow the yellow-brick road from here. (Will award bounty when possible.) $\endgroup$
    – badroit
    Jan 25, 2013 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .