A competition is held between $2^n$ players for some $n > 1$. There are $n$ rounds; in each round the surviving players are paired at random, and the winners advance to the next round. The players are of different levels of ability, and the better players wins each match.
What is the probability that the best four players reach the semi-final?
Similar questions exist on this site but the questions I have come across are structured slightly differently to this one.
I found the probability to be:
$\prod_{k=0}^{n-3} \prod_{j=1}^{4} \left( \frac{2^{n-k} - \left(j+3\right)}{2^{n-k} - 1}\right)$,
but in the case of $n=3$ for example, the denominator remains as 7, and I thought to myself shouldn't the denominator decrease at each iteration?
So out of the eight players, for the best 4 players to reach the semi-final, player 1 can play players 5, 6, 7, or 8 out of players 2, 3, 4, 5, 6, 7, 8 (the reason player 1 cant play players 2, 3, or 4 is because the best four players need to reach the semi final). Say player 1 plays player 5, then player 2 can play either player 6, 7, or 8, out of players 3, 4, 6, 7, 8 (so 5 possibilities, down from 7 from the first scenario, and this is why I was confused as to why the denominator remains 7 and does not decrease). Then this continues for players 3 and 4, where the players they can possibly play decreases each time. So why is the probability the best four players reach the semi final not 4/7 x 3/5 x 2/3 x 1?
I don't think there's any difference between your problem and a very similar problem where the players are randomly thrown into a binary tree, which is then used to form pairings at each round. In that problem:
Player $1$ can go anywhere.
Once we know where Player $1$ has been assigned, out of the $2^n-1$ remaining slots, $3 \cdot 2^{n-2}$ of them are permissible.
If Players $1$ and $2$ have received permissible assignments, then out of the $2^n-2$ remaining slots, $2^{n-1} = 2 \cdot 2^{n-2}$ of them are permissible.
Finally, if the first three players have received permissible assignments, then out of the $2^n-3$ remaining slots, $2^{n-2}$ of them are permissible.
So the probability that I get is:
$$6 \frac{2^{3n-6}}{\prod_{k=1}^3 (2^n-k)}.$$
That's going to have some odd numbers in the denominator.