Counting BracketsDiscrete Mathematics Level 5
Suppose we have \(2^n\) competitors in a single-elimination tournament bracket. While they may be seeded in any conceivable permutation, suppose further that there is a fixed, hidden, strict order of skill amongst the players, such that the winner of any single match is deterministic, and the property is transitive: If \(A\) can beat \(B\), and \(B\) can beat \(C\), then \(A\) can beat \(C\).
The number of distinct ways such a tournament can be seeded is, trivially, \((2^n)!\), but what about the number of distinct ways such a tournament can play out? For example, a 2-person tournament can only ever finish one way: With the best player finishing first, and the other second. A four-person tournament is more interesting. The best player will always finish first, but depending on the seeding, it might be the case that the second-best player finishes second, or the third-best player finishes second, with the remaining players taking an equivalent "3rd/4th" place in the final standings.
Thus, there are precisely 2 ways a 4-person tournament might conclude. More precisely speaking, two tournaments are said to conclude differently if and only if there exists at least one player who got a different placement between the two outcomes. Places in a tournament are, uniquely and distinctly, '1st', '2nd', '3rd-4th', '5th-8th', '9th-16th', etc. etc.
There are 28 ways that an 8-person tournament might conclude, depending on seeding.
How many ways can a 64-person tournament conclude?