1
$\begingroup$

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!

1 Answers 1

1

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!}. } $

  • 0
    @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.2011-11-27