$n$ friends get together and decide to play a game. Thankfully one friend has a deck of $n$ cards, numbered from $1$ to $n$.
How the Game Works
- The group splits into pairs (the game only works when $n$ is even)
- Everyone draws a card
- In each pair, the person who drew a card with a higher number wins (yay!)
- Winners are recorded and who drew which card is recorded
- Cards are collected and shuffled
- Repeat steps 1-5 for $m$ rounds
- Publish the final rankings in order of wins
The Question
My question is about looking at all the possible ways the game could have played out if people would have paired up differently. There are $(n - 1)!!$ possible ways people could have paired up in a given round. Which means that over $m$ rounds, there could have been $(n - 1)!!^m$ ways for the game to have played out
The next time the group plays the game, they decide that everyone has to pair up with each other roughly the same number of times. The maximum and minimum number of times two people can pair up is as follows
$$\text{max} = \left\lceil \frac{m}{n-1} \right\rceil$$ $$\text{min} = \left\lfloor \frac{m}{n-1} \right\rfloor$$
With this new rule, how many possible ways could the game have played out?
Let's call this number $P_n$. It is quite obvious, that $P_2 = 1$. Now, suppose $n > 2$. Then we know, that the $n$-th player paired with $m\%(n - 1)$ people $\left\lceil \frac{m}{n-1} \right\rceil$ times and with $n - 1 - (m\%(n - 1))$ people $\left\lfloor \frac{m}{n-1} \right\rfloor$ times (here $\%$ stands for remainder). He can do that in $C_{n-1}^{m \%(n-1)}$ ways. So $P_n = C_{n-1}^{m \%(n-1)}P_{n - 1} = \Pi_{i = 1}^{n - 1} C_{i}^{m \%i}$.That is the answer.