"In a tennis tournament there are 2n players. In the first round of the tournament each participant plays just once, so there are n games, each occupying a pair of players. Show that the pairing for the first round can be arranged in exactly

1x3x5x7x9x...x(2n-1) different ways."

Just to make it clear, I have access to the answer albeit very short and not as detailed as I worked on the problem. I just want to verify that my reasoning is ok (I relied heavily on geoemetry to make a sense of the product, so my answer is based on this)

We have 2n players. Take one of the players from the group and see how many combinations you can form with the other players. This means you have 2n-1 combinations with the specific player that you chose.

We have (2(n-0)-1) x ....

By what are we going to multiply 2n-1 ? To see this, let us substract 2 from 2n players because this makes sure of accounting of the fact that when we selected one of the players and associated him with the other 2n-1 players that were available, we had different pairs assigned and thus we can disregard each of these unique pairs. Thus, we actually have 2n-2 players and we repeat the same reasoning as before, we select one of these players and assign him to the different other ones, making the number of combinations with this selected player 2n-3=(2n-2)-1=2(n-1)-1.

We have (2(n-0)-1) x (2(n-1)-1) x ...

You repeat the same idea and get :

(2(n-0)-1) x (2(n-1)-1) x (2(n-2)-1) ...

We see a pattern and that all ours numbers are of the form 2n-1 and are thus odd numbers and that these odd numbers are decreasing because we are substracting 0, 1, 2, etc. from n. Thus it goes to 1.

(2(n-0)-1) x (2(n-1)-1) x (2(n-2)-1) x ... x 1

In shorthand : 2(n-a)-1 where n is random and a=0,1,2,3,...,n-1 to make sure n is bigger than a.

Like I said, this is very geometric and this my reasoning of how to solve the problem. The book solution is very very short. I can put it people want to see it.


Note that your number is $p=(2n-1)(2n-3)(2n-5)...1$

If we insert the intermediate even numbers $q=2n(2n-2)...2\quad$ we get $pq=(2n)!$

But $q=2(n)2(n-1)...2(1)=2^nn!\quad$ so $\displaystyle{p=\frac{(2n)!}{n!2^n}=\frac{\mathsf{C_{2n}^n}}{2^n}}$

This $p$ can be interpreted as chosing $(n)$ players among $(2n)$ and dividing by $2$ for each generated pair because game $(a,b)$ is same than game $(b,a)$ (unordered pairing, no return match).

But there is something missing, you have chosen $(n)$ players but not their opponents. There are still $(n)$ players unassigned and $(n!)$ permutations of them.

So after this shuffling, you can pair them one by one with the already chosen players.

Finally you get $\displaystyle{r=n!\times p=\frac{(2n)!}{2^n}}$ possible pairings.

But in fact the order of the $n$ matches is unimportant so we have to divide by $n!$ and obviously we get back to $p$ as expected.

This result $r$ can also have been reached like the following:

Take $(2n)$ players, shuffle them with one of the $(2n)!$ permutations and pair them two by two as they come, divide each pairing by $2$ for the reason already mentioned of unordered pairs (so divide globally by $2^n$).

You could see it also as, choosing two players among $(2n)$ and pair them : this gives $\displaystyle{\mathsf{C_{2n}^{2}}}$.

You continue by choosing two players among $(2n-2)$, then $(2n-4)$, and so on.

Finally $\displaystyle{s=\mathsf{C_{2n}^{2}}\mathsf{C_{2n-2}^{2}}\mathsf{C_{2n-4}^{2}}...\mathsf{C_{2}^{2}}}$ but since $\mathsf{C_{2n}^{2}}=\frac{(2n)(2n-1)}{2}$

You get back to the same result $s=r$.

As you can see in these methods we always have to ultimately divide by $(n!)$ because the pairings order themselves is not important.

In your solution the choice of the first player of the pair is omitted. You indicated the number of way to choose opponents, but not the number of ways to choose the first player.

If you would do that you would get : $\#1$ player, $(2n)$ choices, his opponent $(2n-1)$ choices, $\#3$ player, $(2n-2)$ choices, his opponent $(2n-3)$ choices, and so on...

So these are $(2n)!$ choices, but again choosing $\#1$ first, then $\#2$ or in the opposite order results in the same match, so we have to divide by $2$ (and globally by $2^n$).

And you get same result than $r$ above.

What's make your solution arrive directly at $p$ instead of $r$ is subtle, when you say "take one of the player" you implicitely ignore the permutation of these $n$ choices, resulting in a global division by $(n!)$.

  • $\begingroup$ Sorry, I'm not sure of following. I'm really happy that you took your time to answer my question. But why do you think my answer is not correct ? It literally corresponds to the product that I was supposed to derive, right ? That's what was asked to find.Thanks! Look, I found this one which is word for word what I was asking : math.stackexchange.com/questions/361264/… $\endgroup$ – copper Mar 6 '17 at 21:16
  • $\begingroup$ Your answer is correct, I'm showing you many ways to arrive to the same result and explain it in details for all. The aim was to show the relationships between the different methods. The correct result is effectively $p$ or $r/n!$ by the other methods. $\endgroup$ – zwim Mar 6 '17 at 21:19
  • $\begingroup$ What do you think about my reasoning at arriving at the solution ? I lost myself in your text to be honest lol By the way, I really appreciate the effort in your answer ! $\endgroup$ – copper Mar 7 '17 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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