# number of pairings of 2m objects with constraint

• Jun 4th 2013, 07:56 AM
mnov
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.
• Jun 4th 2013, 08:07 AM
Plato
Re: number of pairings of 2m objects with constraint
Quote:

Originally Posted by mnov
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?
• Jun 4th 2013, 08:28 AM
mnov
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)!!$.
• Jun 4th 2013, 08:54 AM
Plato
Re: number of pairings of 2m objects with constraint
Quote:

Originally Posted by mnov
$\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?
• Jun 4th 2013, 09:18 AM
mnov
Re: number of pairings of 2m objects with constraint
Quote:

Originally Posted by Plato
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$.

Quote:

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.
• Jun 4th 2013, 10:14 AM
Plato
Re: number of pairings of 2m objects with constraint
Quote:

Originally Posted by mnov
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.
• Jun 4th 2013, 10:30 AM
mnov
Re: number of pairings of 2m objects with constraint
Quote:

Originally Posted by Plato
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.
• Jun 4th 2013, 10:44 AM
Plato
Re: number of pairings of 2m objects with constraint
Quote:

Originally Posted by mnov
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.
• Jun 7th 2013, 07:05 AM
mnov
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$