# Counting all possible combinations of a playoff tournament

I have a question about a chess tournament, and I need to count all possible different tournaments. It's a playoff so that after the first round there are $2^n$ players, after the second round there are $2^{(n-1)}$ and so on....

So, how do I count it? Thanks!

-

For a tournament starting with $2^n$ players, let $A_n$ be the number off all possible match results. That is, $A_n$ is the number of different player pools for the next round.

So, I am calling two tournaments different if there is a round where the player pools are different. I am ignoring the different ways for which a particular player pool in round $i$ can be obtained from the games played in the previous round.

Then $A_{n+1} = B_{n+1}\cdot A_n$, where $B_{n+1}$ is the number of different match results in the first round of a tournament with $2^{n+1}$ players.

Now, $B_n= { 2^n\choose 2^{n-1}}$.

$A_1$=2

$A_2= B_2 \cdot A_1= { { 4\choose 2}}\cdot 2$

$A_3= B_3\cdot A_2= {8\choose 4} \cdot { { 4\choose 2}}\cdot2$

$A_4= B_4\cdot A_3={16\choose 8}\cdot {8\choose 4}\cdot { { 4\choose 2}}\cdot2$

$\ \ \ \vdots$

$A_n={2^n\choose 2^{n-1}}\cdot{2^{n-1}\choose 2^{n-2}}\cdot\cdots\cdot{8\choose 4} \cdot { { 4\choose 2}}\cdot2$.

Of course, the above can be simplified considerably:

Note that $2^n-2^{n-1}=2^{n-1}$.

So ${ 2^n\choose 2^{n-1}}={(2^n)!\over (2^{n-1})!(2^{n-1})!}$, and we have: \eqalign{ A_n&= {(2^n)!\over (2^{n-1})! (2^{n-1})!}\cdot{(2^{n-1})!\over(2^{n-2})!(2^{n-2})!}\cdot\cdots\cdot{8!\over 4!\cdot4! } \cdot { { 4!\over 2!\cdot2!}}\cdot2 \cr &= {(2^n)!\over (2^{n-1})!\cdot 1}\cdot{1\over(2^{n-2})!\cdot1}\cdot\cdots\cdot{1\over 4!\cdot1 } \cdot { {1\over 2!\cdot1}}\cdot1 \cr &={(2^n)!\over (2^{n-1})!(2^{n-2})!\cdots4!\cdot 2!}. }

-
$n=2$, 4 players, 3 different ways to pair up the players for the 2 games in round 1, 2 possible results in each of the 2 games, I count 12 different 1st rounds (so 24 different tournaments), but your formulas are giving me 6 1st rounds and 12 tournaments. –  Gerry Myerson Nov 27 '11 at 11:30
@Gerry Myerson I assumed half the players are eliminated in each round (as implied by the problem statement). For 4 players a, b, c, d; the possibilities for the players in the next round are ab, ac, ad, bc, bd, cd. So, starting with 4 players, there are 6 possibilities for the second round. For each of these, there are two possible outcomes for the third round. This gives $6\cdot2=12$ possible tournaments. Or am I off? –  David Mitra Nov 27 '11 at 11:45
@Gerry Myerson I see now; I am calling tournaments different if the player pools are different. This may not (and probably isn't) be what is asked for. Thanks for pointing this out. –  David Mitra Nov 27 '11 at 12:26