Given that March Madness is almost here I was trying to figure out the probability of constructing a perfect bracket if you just flipped a coin for every game. I came up with two possible solutions.
The tournament is basically just 63 disjoint events, so (1/2)^63
Alternatively, each round can be viewed as a set of binomial events, in which case I thought that $\binom{64}{32}\binom{32}{16}\binom{16}{8}\binom{8}{4}\binom{4}{2}\binom{2}{1}$ would get me the same answer (each of those is a binomial coefficient)
However, each of these gives substantially different results. Googling for answers suggests that the first version is the correct one, as does this post
What are the exact odds of getting a perfect NCAA bracket?
So my question is, why is the second answer so different? It seems like that is also a reasonable description of what's going on, but the answer is multiple orders of magnitude too large.
The answer is too large because you are counting combinations that are not possible in the bracket. Look at just $\binom{4}{2}$ for the semi-finals. Let's say that teams $A$ and $B$ are in the left bracket and play each other in a semi-final game and teams $C$ and $D$ are in the right bracket and play each other in a semi-final game. Then the only possible match-ups we can have for the championship are $A-C$, $A-D$, $B-C$, $B-D$. But $\binom{4}{2} = 6$ because it also counts the match-ups $A-B$ and $C-D$ which are valid choices of a subset but not valid based on the bracket structure.