Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
$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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.