Counting Brackets

Relevant wiki: Combinations - Problem Solving

The nature of a tournament bracket easily lends itself to recursive algorithms and formulas to compute things about them. In this case, however, there is a much simpler solution, requiring a little combinatorics and a little math on top.

The answer is clearly very, very big, so we need a way to abstract the problem. We need to determine the number of distinct ways there are to categorize the $2^n$ competitors into $n+1$ buckets, each the size of an incremental power of $2$ , but with the added restriction that it must be possible for such an outcome to occur given the hidden skill order! This is what makes the problem tricky.

---

For simplicity, let's number the players in skill order, so that player $1$ beats everyone, player $2$ beats everyone except player $1$ , and player $2^n$ loses to everyone. Now, suppose we already know the number of ways a tournament of $2^{n-1}$ players can play out: How many ways can one of $2^n$ players play out?

After the first round, we have $2^{n-1}$ players, which comprise some subset of the original set, and therefore has its own order. Furthermore, the number of ways the rest of the rounds can play out is independent of how the first round played out: Therefore, we need only determine the number of possible sets of $2^{n-1}$ losers that may occur after the first round, multiplying this by our answer for the smaller tournament bracket yields the answer we want.

Intuitively, one might say that there are $\binom{2k}{k}$ ways to choose the losers from $2k$ players, but this is incorrect - player $1$ could be designated a loser by that logic, and that is impossible! So how many ways are there to pick losers?

---

Suppose we assign each player a color: Red if they're a winner, blue if they're a loser, and then we list the players in skill order, starting with the best. Clearly, the first color must be red, and then the next one can be blue or red, but if it is blue, the third color again must be red. More succinctly, in order for pairings to be determined such that each player's color is fulfilled, it must be the case that, at any index in the list, the number of reds preceding the index is greater than or equal to the number of blues preceding the index. It is also sufficient for a list to be qualifying if this property holds, since one can produce a valid set of pairings by simply iterating directly through the list, collecting winners as they are come across, and doling them out arbitrarily for each loser iterated over.

The number of such lists is equivalent to the number of Dyck words of length $2^n$ , or the number of random walks of length $2^n$ starting at zero, and ending at zero, with equally probable steps of $+1$ and $-1$ , without ever going negative. All of these things are given by the Catalan Numbers .

Therefore, we can define $f(n)$ as the number of ways a tournament of $2^n$ players can finish, as:

$f(1) = 1$

$f(n > 1) = C_{2^{n-1}} \cdot f(n-1)$

$f(n) = \Pi_{k=1}^{n-1} C_{2^{k}}$

Where $\{C_n\}$ are the Catalan Numbers, computed as $C_n = \frac{1}{n+1} \binom{2n}{n}$ .

And $f(6) = C_{32} C_{16} C_8 C_4 C_2 = \boxed{78620747792837680789505546400}$ .