number of pairings of 2m objects with constraint

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

There are distinct balls. of them are colored red, are blue, and the rest are white. How many pairings of the balls can you form such that they do not contain any {red,blue} pair? I know that if , the answer is .

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

distinct balls.

of them are colored red,

are blue, and the rest are white. How many pairings of the

balls can you form such that they do not contain any {red,blue} pair? I know that if

,

the answer is .

How is the notation defined?

And where did you get that answer?

Re: number of pairings of 2m objects with constraint

When , the problem simplifies to that of pairing distinct objects. Arrange the balls in a straight line. This can be done in 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 ) and rearranging the pairs (a factor of ) lead to the same pairing. So the total number of pairings is .

Re: number of pairings of 2m objects with constraint

Quote:

Originally Posted by

**mnov**
When

, the problem simplifies to that of pairing

distinct objects. Arrange the balls in a straight line. This can be done in

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

) and rearranging the pairs (a factor of

) lead to the same pairing. So the total number of pairings is

.

Thank you for the explanation. Interesting notation. I don't recall having seen it before.

The **total parings** without restrictions is .

Is it clear that 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

.

Is it clear that

and are only restricted to be .

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 be the number of ways of forming a partition that contains exactly {red,red} pairs, {blue,blue} pairs, and {red,blue} pairs. An algorithm to calculate is as follows

- use the red balls to form {red,red} pairs; number of ways
- use the blue balls to form {blue,blue} pairs; number of ways
- now there are red and blue balls; use them to form {red,blue} pairs;
- now there are red, white balls; use them to form {red,white} pairs;
- now there are blue, white balls; use them to form {blue,white} pairs;
- now there are white balls; use them to form {white,white} pairs;

Soution to the original problem

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

where