Let n players enter a chess tournament. How many tournament trees are possible?
RULES: a player is eliminated after one loss and games are played until only one entrant is left(assume no ties)
My approach: (please check if it is correct)
there are 3 possible binary tree skeletons w.r.t. n:
- n = 2^k
- n = 2k
- n = 2k-1
k>=1
we have to make cases for each of these models
- if n = 2^k
initial round = leaf nodes
nC2 * (n-2)C2 * (n-4)C2 *...*1
next round = degree 2 nodes
2*2*2*2...*2
and so on till the root (winner)
now, multiply all the above-level results-
{nC2 * (n-2)C2 * (n-4)C2 *...*1} * 2^(n-1)
similarly we can do the remaining cases.
Is the above method right?
