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.

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?

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)!!$.

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?

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.

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.

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.

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.

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$