Results 1 to 4 of 4

Math Help - Number of different pairings of 2n objects.

  1. #1
    Junior Member
    Joined
    Dec 2010
    Posts
    61

    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
    Last edited by mr fantastic; November 21st 2011 at 02:22 AM. Reason: Re-titled.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Number of different pairings of 2n objects.

    Quote Originally Posted by Mathsdog View Post
    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!.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Flatiron's Avatar
    Joined
    Dec 2010
    From
    AZ
    Posts
    9

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2011
    Posts
    53
    Thanks
    1

    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!}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of derangements of n objects
    Posted in the Math Challenge Problems Forum
    Replies: 10
    Last Post: February 10th 2010, 08:16 AM
  2. Probability pairings
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 29th 2009, 07:08 AM
  3. Replies: 10
    Last Post: May 28th 2009, 10:25 AM
  4. Marriage Pairings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 16th 2008, 06:26 PM
  5. Pairings problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 17th 2007, 06:36 AM

Search Tags


/mathhelpforum @mathhelpforum