# number of pairings of 2m objects with constraint

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

Originally Posted by mnov
$(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?
• Jun 4th 2013, 10: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 $\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$.

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, 11: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, 11: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, 11: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, 08:05 AM
mnov
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$