Assume you have 4 people or teams in a tournament. There will be three games:
3
1 2
a b c d
The people/teams in this case are the letters, and 3 (i.e., $n – 1$) games must be played. The only requirement is that games 1 and 2 must happen before game 3. Below are the possible orderings that the games can be played:
- 12 | 3
- 21 | 3
Simple enough. Now let's say there are 8 players/teams, and therefore 7 total games. We'll have two trees the same size as above:
7
3 6
1 2 4 5
Each total ordering will be of format xxxxxx7, but the number of orderings will clearly not be the number of ways to arrange 6 items ($6!$), because we have some requirements:
- Game 6 must be before both games 4 and 5
- Game 3 must be before both games 1 and 2
So we have the two sets of orderings for each tree, ($(123, 213)$, and $(456, 546)$), and we somehow have to merge them. We can't just take the cartesian product of the two sets though, because we have to account for the game orderings to be intertwined (orderings like $1423567$)
This feels very factorial-esque but I'm not entirely sure how to treat the restrictions. For example any one of 4 possible games can be played first:
4 * _ * _ * _ * _ * _
Any one of 3 possible games can be played second:
4 * 3 * _ * _ * _ * _
But for the third game, some combinations up to this point have 3 possibilities, and some have 2, which makes the rest complex. I'm not sure how to extend the "merging" or the math in this case, to either:
- Find the number of total orderings of $n$ games ($n + 1$ players)
- Actually generate all possible combinations of $n$ games
Best Answer
Okay, let me take a stab at this. I'll assume the problem is restricted to having exactly $2^n$ teams in the tournament.
Clearly, the top game must happen after all the other games. Then we have two subproblems to solve with $2^{n-1}$ teams each. Supposing that we can solve each subproblem, we want to know how many ways there are to interleave two independent solutions for the $2^{n-1}$ team case. There are $2^{n-1}-1$ games in the left subsolution and $2^{n-1}-1$ games in the right subsolution. We can take these in any order, so essentially we want to know the number of ways there are of arranging the letters "L" and "R" where there are $2^{n-1}-1$ of each. This should be $\frac{(2^{n}-2)!}{(2^{n-1}-1)!(2^{n-1}-1)!}$.
So, we now have enough to define a recursive function $f(n)$ that solves this problem. We interpret $f(n)$ to be the number of possible orderings of games in a tournament with $2^n$ teams.
$$ f(n) = \begin{cases}1 & \text{ if } n=1\\ \frac{(2^{n}-2)!}{(2^{n-1}-1)!(2^{n-1}-1)!}(f(n-1))^2 & \text{otherwise} \end{cases} $$
(We get the $(f(n-1))^2$ from the $f(n-1)$ possible combinations for each subproblem.)