3
$\begingroup$

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
$\endgroup$
  • $\begingroup$ +1 very nice question $\endgroup$ – the_candyman Oct 21 '18 at 21:36
  • $\begingroup$ just to make things clearer... if $a$ and $b$ will produce the winner $c$ in a match, then a correct string must be in the forms $...ab...c...$ or $...ba...c...$, right? I mean, $a$ and $b$ must be consecutive, or it is sufficient that both appear before $c$ (so that strings like $...a...b...c...$ and $...b...a...c...$ are feasible too)? $\endgroup$ – the_candyman Oct 21 '18 at 21:41
  • $\begingroup$ @the_candyman yeah, the way you're writing it, "ab" would need to be consecutive; I prefer to think of it as numbered games though, because saying "c" is the winner of "ab" is awkward when "cd" is a separate match. I see what you're saying, but yeah, n - 1 games, so I'm interested in how many ways the n - 1 game numbers can be ordered $\endgroup$ – Dominic Farolino Oct 21 '18 at 21:45
  • 1
    $\begingroup$ This may be interesting to you: en.wikipedia.org/wiki/Topological_sorting I don't know if there's any general method to count the number of solutions, though. $\endgroup$ – Ricky Tensor Oct 21 '18 at 21:45
  • 1
    $\begingroup$ @RickyTensor Ahh that's right it is essentially generating all topological orderings. Looking at this now: geeksforgeeks.org/… $\endgroup$ – Dominic Farolino Oct 21 '18 at 21:51
2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Wow, I think that's right! Let me try and verify $\endgroup$ – Dominic Farolino Oct 21 '18 at 22:25
  • $\begingroup$ Can you explain the sentence "We can take these in any order" please? If the left subproblem has 3 games (4 players), and so does the right, "any order" sounds like 6!, which is where you get your numerator, but I'm curious how you got the denominator, which apparently eliminates invalid left- and right-subproblem-orderings. I guess you're saying there are $2^{n - 1} - 1$ left- (same for right) games, so we eliminate all of their limited possible orderings for each ($(2^{n - 1} - 1)!$ for one side), and make up for the orderings that we removed that were valid, by recursing? $\endgroup$ – Dominic Farolino Oct 21 '18 at 22:51
  • $\begingroup$ Ah, I see, so math.stackexchange.com/questions/382174 explains the number of ways we can interleave two subordeirngs, and then recursing is how we get the number of actual suborderings for each side. brilliant! $\endgroup$ – Dominic Farolino Oct 21 '18 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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