# Sample space of possible outcomes for a knockout tournament

I would like to confirm if my answer is correct for the following question:

A conventional knock-out tournament begins with $2^n$ competitors and has $n$ rounds. There are no play-offs for the positions $2,3,..,2^{n-1}$, and the initial table of draws is specified. Give a concise description of the sample space of all possible outcomes.

My answer is: $$\sum_{i=1}^{n} 2^{2^{i}/2}.$$

My reasoning is as follows: For each round, the number of players is $2^n$. The number of matches for each round is $2^n / 2$. Since there can be only a win or loss, the total number of combinations per round is $2^{2^{n}/2}$. Therefore the total number of combinations of outcomes (the total sample space), is the sum of combinations in each round from $1 \ldots n$.

-
What is the variable in the summation? –  vadim123 Feb 18 '14 at 17:58
Corrected the summation. –  I.K. Feb 18 '14 at 18:00
"For each round, the number of players is $2^n$": No it's not. –  TonyK Feb 18 '14 at 18:04

You don't need to sum any complicated series here. Simply observe that each match eliminates one competitor, therefore there are $2^n-1$ matches, each of which has two possible outcomes.

-
No! Much more than that! –  TonyK Feb 18 '14 at 18:38
Answer is: $2^{2^{n} - 1}$. –  I.K. Feb 18 '14 at 18:52

We have $2^n$ players, so basically there are $\frac{2^n}{2} = 2^{n-1}$ games in the first round. The combination of possible players going to the next round is given by $2^{2^{n-1}}$ because in each game we have two possible winners.

In the second round, we will have $2^{n-1}$ players and $2^{n-2}$ games. Following the same reasoning, the combination of winners is given by $2^{2^{n-2}}$.

And so on, until we reach the final, for which we have $2^1$ possible winners.

Therefore, the number of possibilities we have is given by the summation of all possible outcomes in different rounds:

$\displaystyle \sum_{i=1}^{n} 2^{2^{n-i}}$.

If we take only the power, we can see that it follows a geometric series form, so we can calculate the sum of all powers $= 2^n - 1$

Therefore, the final number of possibilities is $2^{2^n - 1}$.

The explanation of Tony K is much simpler, however I couldn't figure out why the number of games was $2^n - 1$ until I developed this reasoning.

Hope it helps!

-