Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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.., –  gnometorule Jan 22 '13 at 18:25
    
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.) –  badroit Jan 22 '13 at 18:27
1  
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. :) –  gnometorule Jan 22 '13 at 18:31
add comment

1 Answer

up vote 4 down vote accepted
+50

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.

share|improve this answer
    
Perfect, thanks! I can follow the yellow-brick road from here. (Will award bounty when possible.) –  badroit Jan 25 '13 at 18:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.