Results 1 to 9 of 9

Thread: 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 $\displaystyle 2m$ distinct balls. $\displaystyle r$ of them are colored red, $\displaystyle b$ are blue, and the rest are white. How many pairings of the $\displaystyle 2m$ balls can you form such that they do not contain any {red,blue} pair? I know that if $\displaystyle r=b=0$, the answer is $\displaystyle (2m-1)!!$.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    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 $\displaystyle 2m$ distinct balls. $\displaystyle r$ of them are colored red, $\displaystyle b$ are blue, and the rest are white. How many pairings of the $\displaystyle 2m$ balls can you form such that they do not contain any {red,blue} pair? I know that if $\displaystyle r=b=0$, the answer is $\displaystyle (2m-1)!!$.
    How is the notation $\displaystyle 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

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

    When $\displaystyle r=b=0$, the problem simplifies to that of pairing $\displaystyle 2m$ distinct objects. Arrange the balls in a straight line. This can be done in $\displaystyle (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 $\displaystyle (2!)^m$ ) and rearranging the pairs (a factor of $\displaystyle m!$ ) lead to the same pairing. So the total number of pairings is $\displaystyle \frac{(2m)!}{(2!)^m m!} = (2m-1)!!$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1

    Re: number of pairings of 2m objects with constraint

    Quote Originally Posted by mnov View Post
    $\displaystyle (2m-1)!! = 1 \times 3 \times \ldots \times (2m-1)$
    When $\displaystyle r=b=0$, the problem simplifies to that of pairing $\displaystyle 2m$ distinct objects. Arrange the balls in a straight line. This can be done in $\displaystyle (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 $\displaystyle (2!)^m$ ) and rearranging the pairs (a factor of $\displaystyle m!$ ) lead to the same pairing. So the total number of pairings is $\displaystyle \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 $\displaystyle \frac{(2m)!}{(2!)^m m!}$.
    Is it clear that $\displaystyle 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 $\displaystyle \frac{(2m)!}{(2!)^m m!}$.
    Is it clear that $\displaystyle r+b\le m~? $
    $\displaystyle r$ and $\displaystyle b$ are only restricted to be $\displaystyle 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
    21,796
    Thanks
    2827
    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
    21,796
    Thanks
    2827
    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 $\displaystyle N(R,B,D)$ be the number of ways of forming a partition that contains exactly $\displaystyle R$ {red,red} pairs, $\displaystyle B$ {blue,blue} pairs, and $\displaystyle D$ {red,blue} pairs. An algorithm to calculate $\displaystyle N$ is as follows
    • use the $\displaystyle r$ red balls to form $\displaystyle R$ {red,red} pairs; number of ways $\displaystyle =N_1 = \binom{r}{2R} (2R-1)!!$
    • use the $\displaystyle b$ blue balls to form $\displaystyle B$ {blue,blue} pairs; number of ways $\displaystyle =N_2 = \binom{b}{2B} (2B-1)!!$
    • now there are $\displaystyle (r-2R)$ red and $\displaystyle (b-2B)$ blue balls; use them to form $\displaystyle D$ {red,blue} pairs; $\displaystyle N_3 = \binom{r-2R}{D} \binom{b-2B}{D} D!$
    • now there are $\displaystyle (r-2R-D)$ red, $\displaystyle (2m-r-b)$ white balls; use them to form {red,white} pairs; $\displaystyle N_4 = \binom{2m-r-b}{r-2R-D} (r-2R-D)! $
    • now there are $\displaystyle (b-2B-D)$ blue, $\displaystyle [(2m-r-b)-(r-2R-D)]$ white balls; use them to form {blue,white} pairs; $\displaystyle N_5 = \binom{(2m-r-b)-(r-2R-D)}{b-2B-D} (b-2B-D)!$
    • now there are $\displaystyle [(2m-r-b)-(r-2R-D)-(b-2B-D)]$ white balls; use them to form {white,white} pairs; $\displaystyle N_6 = [(2m-r-b)-(r-2R-D)-(b-2B-D)-1]!!$


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

    Soution to the original problem $\displaystyle = \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
    $\displaystyle N[0,0,0] = \frac{(m+k)!}{k! 2^k}$ where $\displaystyle 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: Jun 3rd 2013, 04:11 PM
  2. Distinct objects vs Indistinct objects
    Posted in the Statistics Forum
    Replies: 0
    Last Post: Feb 20th 2013, 09:30 AM
  3. Number of different pairings of 2n objects.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 21st 2011, 10:33 AM
  4. Number of derangements of n objects
    Posted in the Math Challenge Problems Forum
    Replies: 10
    Last Post: Feb 10th 2010, 08:16 AM
  5. Replies: 10
    Last Post: May 28th 2009, 10:25 AM

Search Tags


/mathhelpforum @mathhelpforum