Ways To Order Matches - Six Nations

Question

There are $n$ teams in a sports tournament, and each team has to play every other team, and all teams have to play every weekend over $n-1$ weekends.

For example, rugby six nations $n=6$ pretty much follows this pattern.

Hoe many ways are there to uniquely order the matches?

Note: we are not counting home vs away matches as different. But a bonus question would be to calculate the number of unique ordering where home and away are treated differently.

My Attempt

I believe the answer is:

$\prod_{k=1}^{n-1} k! = \prod_{k=1}^{n-1} k^{n-k}$

Any team has $(n-1)!$ ways to sequence who they play each weekend. The next team has $(n-2)!$ ways for the remaining matches excluding the first team etc.

If you care about order within a weekend multiply the above by $(\frac{n}2)!$. This is always defined as $n$ is guaranteed to be even.

Problem: Overcounting occurs with the above assumption of a choice algorithm. We can see why by counterexamlple (thanks to commenter).

• A chooses: Ab, ac, ad, ae, af
• B chooses (a fixed): Ab, ac-bd, ad-bc, ae-bf, af-be

At this point, the above incorrect maths assumes that c has got $3!$ choices with ab out of the picture. But it doesn't: it has none. c MUST choose D on the fourth weekend AND the fifth weekend in the above example, an absurdity, meaning this entire choice tree counts for zero states in our state space that were trying to count.

Given how easy it seems for constraints like this to arise naturally I imagine the number of unique orderings is much smaller than I originally thought.

Answer 1

Here’s Java code that counts these schedules by enumueration. The result is OEIS sequence A036981, which gives the counts for up to $14$ teams. The entry’s title is “Number of $(2n+1)\times(2n+1)$ symmetric matrices each of whose rows is a permutation of $1\ldots(2n+1)$”, where $2n+1$ corresponds to your $n-1$.

As discussed in the comments, my original suggestion for converting such a matrix into a tournament schedule turned out to be wrong, whereas the OP’s suggestion works: The matrix entries specify the weekend on which the row and column teams play each other, except the diagonal (since a team doesn’t play itself), which specifies when the teams play the $n$-th team not represented by a row or column.

For this to work, the diagonal must also contain a permutation of the teams. This is indeed the case, since every team appears an odd number of times in the matrix (once in each row, whose number is odd) and an even number of times off the diagonal (by symmetry) and hence at least once, and hence exactly once, on the diagonal.

The OEIS entry contains a reference and a link to a related entry with further references, but no closed form or generating function.

Answer 2

Already answered here: 1. Using this answer to share some additional facts.

Let $n$ be some even natural number.

Let $S(n)$ be the set of all schedules for $n$ teams.

Let $f(n)$ denote the number of ways to schedule $n$ teams. $f(n) = |S(n)|$.

Conjecture: A Solution Exists

For all $n \geq 2$, there is some $s \in S(n)$.

CAN ANYBODY PROVE THIS?

Lemma: Divisibility By Factorial

There is a positive valued function $g: \mathbb{N} \mapsto \mathbb{N}$ such that:

$$f(n) = g(n) * (n - 1)!$$

Proof: Consider any one team. Remove that team from the group - WLOG let's denote that team as $t_n$. The remaining teams form an ordered sequence $t_1 \dots t_{n-1}$. Consider any schedule $s \in S(n)$ (assuming $S(n)$ is non-empty such $s$ exists - I haven't proved that though). Within that schedule, the order in which $t_n$ plays the other teams forms a permutation of $t_1 \dots t_{n-1}$. The set $S(n)$ can be partitioned into $(n-1)!$ disjoint subsets $S_1, S_2, \dots S_{(n-1)!}$, each subset representing all schedules for the given permutation of $t_1 \dots t_{n-1}$. For any $i, j$, there is a bijective mapping between schedules in $S_i$ and those in $S_k$ - simply apply the given permutation on $t_1 \dots t_{n-1}$ as a substitution function. Therefore, there is some $g(n)$ such that $|S_k| = |S_i| = g(n)$, and assuming at least one valid schedule exists (as stated above), $g(n) > 0$. Therefore:

$$f(n) = |S(n)| = |S_1 \cup S_2 \cup \dots \cup S_{(n-1)!}| = |S_1| \cup |S_2| \cup \dots \cup |S_{(n-1)!}| = g(n) * (n - 1)!$$

Here's a Gist that leverages this fact, building on the earlier answer's Gist.

Lemma: Growth Rate Factorial Bounded

The growth rate of $f$ is bounded below and above by factorials as follows:

$$(n-1)! \leq f(n) \leq {n \choose 2}!$$

The lower bound follows from the factorial divisibility lemma. The upper bound follows from the fact that any valid schedule injectively maps to some permutation of pairs of teams.