Results 1 to 9 of 9

Math Help - number of pairings of 2m objects with constraint

  1. #1
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    number of pairings of 2m objects with constraint

    Could someone help me with this (possibly simple) problem?....

    There are 2m distinct balls. r of them are colored red, b are blue, and the rest are white. How many pairings of the 2m balls can you form such that they do not contain any {red,blue} pair? I know that if r=b=0, the answer is (2m-1)!!.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,820
    Thanks
    1711
    Awards
    1

    Re: number of pairings of 2m objects with constraint

    Quote Originally Posted by mnov View Post
    Could someone help me with this (possibly simple) problem?....
    There are 2m distinct balls. r of them are colored red, b are blue, and the rest are white. How many pairings of the 2m balls can you form such that they do not contain any {red,blue} pair? I know that if r=b=0, the answer is (2m-1)!!.
    How is the notation N!! defined?

    And where did you get that answer?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: number of pairings of 2m objects with constraint

    (2m-1)!! = 1 \times 3 \times \ldots \times (2m-1)

    When r=b=0, the problem simplifies to that of pairing 2m distinct objects. Arrange the balls in a straight line. This can be done in (2m)! ways. In each arrangement, pairs are formed by pairing adjacent balls. Once this is done, swaping the position of balls within each pair ( a factor of (2!)^m ) and rearranging the pairs (a factor of m! ) lead to the same pairing. So the total number of pairings is \frac{(2m)!}{(2!)^m m!} = (2m-1)!!.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,820
    Thanks
    1711
    Awards
    1

    Re: number of pairings of 2m objects with constraint

    Quote Originally Posted by mnov View Post
    (2m-1)!! = 1 \times 3 \times \ldots \times (2m-1)
    When r=b=0, the problem simplifies to that of pairing 2m distinct objects. Arrange the balls in a straight line. This can be done in (2m)! ways. In each arrangement, pairs are formed by pairing adjacent balls. Once this is done, swaping the position of balls within each pair ( a factor of (2!)^m ) and rearranging the pairs (a factor of m! ) lead to the same pairing. So the total number of pairings is \frac{(2m)!}{(2!)^m m!} = (2m-1)!!.
    Thank you for the explanation. Interesting notation. I don't recall having seen it before.

    The total parings without restrictions is \frac{(2m)!}{(2!)^m m!}.
    Is it clear that r+b\le m~? How many of those are a red/blue pair?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: number of pairings of 2m objects with constraint

    Quote Originally Posted by Plato View Post
    Thank you for the explanation. Interesting notation. I don't recall having seen it before.

    The total parings without restrictions is \frac{(2m)!}{(2!)^m m!}.
    Is it clear that r+b\le m~?
    r and b are only restricted to be r+b\le 2m.

    How many of those are a red/blue pair?
    I'm sorry, but I'm not sure I understood your question. The problem is to find the number of pairings that contain no {red, blue} pair.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,820
    Thanks
    1711
    Awards
    1

    Re: number of pairings of 2m objects with constraint

    Quote Originally Posted by mnov View Post
    I'm sorry, but I'm not sure I understood your question. The problem is to find the number of pairings that contain no {red, blue} pair.
    These are known as unordered partitions. You clearly understand how to count them.

    What I was trying to suggest is then finding the number of those partitions which contain at least one red/blue pair. If that can be done then that number can be removed from the total. That will answer the question.

    Now I understand that alone can be quite involved using the inclusion/exclusion principle. I have not tried to think it through. It seems to involve several cases.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: number of pairings of 2m objects with constraint

    Quote Originally Posted by Plato View Post
    These are known as unordered partitions. You clearly understand how to count them.

    What I was trying to suggest is then finding the number of those partitions which contain at least one red/blue pair. If that can be done then that number can be removed from the total. That will answer the question.

    Now I understand that alone can be quite involved using the inclusion/exclusion principle. I have not tried to think it through. It seems to involve several cases.
    Actually, the number of partitions that contain at least one red/blue pair is the problem that I'm really interested in, but didn't have any success.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,820
    Thanks
    1711
    Awards
    1

    Re: number of pairings of 2m objects with constraint

    Quote Originally Posted by mnov View Post
    Actually, the number of partitions that contain at least one red/blue pair is the problem that I'm really interested in, but didn't have any success.
    That is really funny. You ought to ask the true question to begin with.

    Inclusion/exclusion is way to go. But that will be difficult given the distinct balls and different colors.

    I would not like to work through it.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jun 2013
    From
    United States
    Posts
    28
    Thanks
    5

    Re: number of pairings of 2m objects with constraint

    I think I have found a long (and ugly) solution.

    Let N(R,B,D) be the number of ways of forming a partition that contains exactly R {red,red} pairs, B {blue,blue} pairs, and D {red,blue} pairs. An algorithm to calculate N is as follows
    • use the r red balls to form R {red,red} pairs; number of ways =N_1 = \binom{r}{2R} (2R-1)!!
    • use the b blue balls to form B {blue,blue} pairs; number of ways =N_2 = \binom{b}{2B} (2B-1)!!
    • now there are (r-2R) red and (b-2B) blue balls; use them to form D {red,blue} pairs; N_3 = \binom{r-2R}{D} \binom{b-2B}{D} D!
    • now there are (r-2R-D) red, (2m-r-b) white balls; use them to form {red,white} pairs; N_4 = \binom{2m-r-b}{r-2R-D} (r-2R-D)!
    • now there are (b-2B-D) blue, [(2m-r-b)-(r-2R-D)] white balls; use them to form {blue,white} pairs; N_5 = \binom{(2m-r-b)-(r-2R-D)}{b-2B-D} (b-2B-D)!
    • now there are [(2m-r-b)-(r-2R-D)-(b-2B-D)] white balls; use them to form {white,white} pairs; N_6 = [(2m-r-b)-(r-2R-D)-(b-2B-D)-1]!!


    N = N_1 \times N_2 \times N_3 \times N_4 \times N_5 \times N_6

    Soution to the original problem = \sum_{R} \sum_{B} N(R,B,0)

    Don't know how to get a closed form to the double sum above. At least I couldn't get Mathematica to do it.

    The solution to the problem where {red,blue},{red,red} and {blue, blue} pairs are disallowed looks nicer
    N[0,0,0] = \frac{(m+k)!}{k! 2^k} where k = m-r-b
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number of partitioning identical objects
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 3rd 2013, 04:11 PM
  2. Distinct objects vs Indistinct objects
    Posted in the Statistics Forum
    Replies: 0
    Last Post: February 20th 2013, 09:30 AM
  3. Number of different pairings of 2n objects.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 21st 2011, 10:33 AM
  4. Number of derangements of n objects
    Posted in the Math Challenge Problems Forum
    Replies: 10
    Last Post: February 10th 2010, 08:16 AM
  5. Replies: 10
    Last Post: May 28th 2009, 10:25 AM

Search Tags


/mathhelpforum @mathhelpforum