# Combinatorics: Does this method take into account every possible matchup

It's actually a question on finding the probability, but I am stuck on a different part of this question. There are $2^n$ players playing a tennis tournament. I have to find the total number of ways in which semifinalists are selected. The answer provided to me is $^{2^n}C_4$. But I think this is wrong.

Let the players which are selected be A,B,C and D. Now, if in the first round, A plays against E and B against F, consider the case where A plays against F and B against E. Is this match-up taken into account by the given answer?

If yes, please try to explain it to me and if no, what is the correct answer?

• No. $^{2^n}C_4$ is only the number of ways of choosing $4$ players from $2^n$ players. It does not take into account how they are chosen (or the matches) Commented Feb 6, 2016 at 5:53
• We should go back to the probability problem. If all tournament trees are equally likely (so random seeding, and any match is equally likely to result in a win by either player) then the probability A, B, C, D reach the Final Four is indeed the reciprocal of the number you mentioned. Commented Feb 6, 2016 at 5:54
• @AndréNicolas I think I understand what you mean. For each set of four players that qualify for the semifinals, the number of pairings are same, so the common term will be cancelled out from the numerator and denominator in the probability. So that part's clear to me now. But still, I want to find the number of ways to select semifinalists. Commented Feb 6, 2016 at 6:00
• If you want the total number of possible tournament histories, this is very large. There are $2^{n-1}$ first round matches, so $2^{2^{n-1}}$ possible outcomes. For each of these, there are $2^{2^{n-2}}$ possible second round outcomes, and so on. Multiply until you get to $4$ survivors. The multiplication simplifies, since the exponent is a geometric series. Is this what you are asking about, possible histories? Commented Feb 6, 2016 at 6:07
• @Akshit: For an answer, I wrote down a streamlined version of the solution in the comment, one that avoids considering rounds. Commented Feb 6, 2016 at 6:28

Any game eliminates one of the players. So the number of games until all but $4$ of the players are eliminated is $2^n-4$. Each game has two possible outcomes: the "left" player wins or the "right" player wins (or, if you prefer, the player with the smaller student number wins/loses). So the total number of possible histories until $4$ players remain is $2^{2^n-4}$.
Incidentally, answering another possible interpretation of the question: Given an initial seeding of a single-elimination tournament, there are $2^{n-2}$ players in each quarter of the draw, so there are $(2^{n-2})^4 = 2^{4n-8}$ different ways to select semifinalists.