# Thread: Number of different pairings of 2n objects.

1. ## Number of different pairings of 2n objects.

Hi,
A tennis tournament has a field of 2n entrants, all of whom need to be scheduled to play in the first round. How many different pairings are possible?

The solution is ${(2n)!\over{n!(2!)^n}} = 1 \cdot 3 \cdot 5 \cdot . . . \cdot (2n-1)$

But I cant see my way through the logic of this solution.

Thanks for any insights
MD

2. ## Re: Number of different pairings of 2n objects.

Originally Posted by Mathsdog
A tennis tournament has a field of 2n entrants, all of whom need to be scheduled to play in the first round. How many different pairings are possible?
The solution is ${(2n)!\over{n!(2!)^n}} = 1 \cdot 3 \cdot 5 \cdot . . . \cdot (2n-1)$
This is known as an unordered partition.
If we have $k\cdot N$ distinct items we can group these into k groups of N each in $\frac{(kN)!}{(N!)^k(k!)}$ ways.

For example: suppose we have twenty people to divide into four teams of five each. That can be done in $\frac{20!}{(5!)^4(4!)}$.
To see that think of a list of these people.
Make a string "AAAAABBBBBCCCCCDDDDDD".
The number of ways to rearrange that string is $\frac{20!}{(5!)^4}$.
To remove the identity of the groups we divide by $4!$.

3. ## Re: Number of different pairings of 2n objects.

All players play in the first round. Consider Player 1. He has 2n-1 potential opponents. Consider a player who is not paired with Player 1. That player has 2n-3 potential pairings, given that the first pairing has been chosen. After the first two pairings are chosen, consider another not chosen player. That player has 2n-5 potential opponents. Etc.

4. ## Re: Number of different pairings of 2n objects.

If your curious about the derivation of the formula it comes from this:

Consider you have k groups of N people each. The total number of ways you can pick the first team is:
$\binom{k*N}{N} = \frac{(k*N)!}{N! (k*N-N)!}$

Now that we chose the first team. there is k*N-N people left. (we took N people out for the first team.) So the number of ways to pick team 2 is:
$\binom{k*N-N}{N} = \frac{(k*N-N)!}{N! (k*N-2N)!}$

Now that we chose the second team. there is k*N-2N people left. (we took N people out for the second team.) So the number of ways to pick team 3 is:

$\binom{k*N-2N}{N} = \frac{(k*N-2N)!}{N! (k*N-3N)!}$

Now we continue doing this k times. We must multiply all these possibilites together. If not you notice the numerator of each term appears in the denominator of the last term, so it cancels. So we end up with N! in the denominator k times. So our final equation is.

$\frac{(k*N)!}{N!^k}$ Equation 1.

So now we need to look at it like a string of names as flatiron pointed out. Each letter will be repeated N times (since they are in teams of N people). And there will be k teams. (that is k different letters).

AABBCCDDEEFFGG

So Equation 1 tells us all the different ways we can put names into those letters. Assume that in the above list: Player 1 and 2 are As and Player 3 and 4 are Bs. Our ordering will produce a result such that Player 1 and 2 are Bs and Player 3 and 4 are As. This would be the same as listing them like this:

BBAACCDDEEFFGG. For our purposes this is the same as above, because we still have a pairing of 1 vs 2 and 3 vs 4. So we have counted this twice. So we have to divide by how many ways we can list out k letters. That just happens to be k! So our final equation is:

$\frac{(k*N)!}{N!^k k!}$

and for your specific case k=n and N=2 so

$\frac{(2n)!}{2!^n n!}$

,

,

### Find a recurrence relation for the number of ways to pair off 2n peoplefortennis matches.

Click on a term to search for related topics.