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.
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 .
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.
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