## Football Tournaments

32 teams compete in a football tournament.
Initially the teams are sorted randomly into 8 groups with four teams in each. All the teams in each group play each other once, and the top two teams in each group go through to the next stage - the knockout stage, in which teams are randomly selected to play each other. The winner of each game is promoted to the next stage, and teams are randomly selected to play each other, with the winners promoted to the next stage, until the final. The winner of the final wins the tournament.
How many possible combinations are there?
Initially the teams are sorted into groups. Group 1 is filled with 4 of 32 teams - there are
${}^{32}C_4$
possible ways to do this, then group 2 is filled with 4 of the remaining 28 teams - there are
${}^{28}C_4$
possible ways to do this. Carrying on in this way, the groups may be filled in
${}^{32}C_4 \times {}^{28}C_4 \times {}^{24}C_4 \times {}^{20}C_4 \times {}^{16}C_4 \times {}^{12}C_4 \times {}^{8}C_4 \times {}^{4}C_4$

possible ways. IN each group, 2 of 4 teams get to the next stage. Two teams may be chosen from 4 in
${}^{4}C_2$
possible ways. Since there are 8 groups, the 16 teams progressing to the knockout stage may be chosen in
$({}^{4}C_2)^8$
ways.
The first knockout stage consists of 8 games, each with 2 teams. The winners may be chosen in
$2^8$
ways.
The second knockout stage consists of 4 games, each with 2 teams. The winners may be chosen in
$2^4$
ways.
The third knockout stage consists of 2 games, each with 2 teams. The winners may be chosen in
$2^2$
ways.
The final consists of 2 teams so the tournament winner may be chosen in
$2^1$
ways.
Each stage is independent, so the number of possible combinations is
\begin{aligned} & {}^{32}C_4 \times {}^{28}C_4 \times {}^{24}C_4 \times {}^{20}C_4 \times {}^{16}C_4 \times {}^{12}C_4 \times {}^{8}C_4 \times {}^{4}C_4 \\ & \times ({}^{4}C_2)^8 \times 2^8 \times 2^4 \times 2^2 \times 2^1 \end{aligned}