4
$\begingroup$

I've reduced a different problem I have to something that can be explained as below, but I'm not sure how to solve this last part.

Assume there are two bags of colored marbles. Any color in the first bag will not be in the second bag. For example, the first bag has two blue marble and three green marbles, while the second bag has one red marble, one white marble, and three black marbles. Each marble in the first bag has to be paired up with a marble in the second bag. How many different complete pair sets (where every marble is paired with another) are there?

A general solution would be amazing, else a pointer in the right direction would be great.

Thanks for any help!

$\endgroup$
5
  • $\begingroup$ What is a complete pair set? $\endgroup$
    – muzzlator
    Feb 27, 2013 at 20:05
  • $\begingroup$ @muzzlator: Where every marble in the first bag is paired with a marble in the second bag. One such combination of pairs is what I am calling a "complete pair set". $\endgroup$
    – Albeit
    Feb 27, 2013 at 20:21
  • $\begingroup$ Hm but the second bag in your example has only 4 marbles. What would it mean in that case? (Sorry about the delay, I'm on and off) $\endgroup$
    – muzzlator
    Feb 27, 2013 at 21:08
  • $\begingroup$ @muzzlator: Sorry, typo, fixed now. $\endgroup$
    – Albeit
    Feb 27, 2013 at 21:11
  • $\begingroup$ Please let me know if this is wrong. I believe I have a way to calculate the number of pairings but the order or the final pairs matters. $$pairs = \frac{n!^2}{\prod(a_j!)\prod(b_k!)}$$ where $a_j$ and $b_k$ are the components of each bag. This will give the number of possible pairs in a particular order. (aka aA bB is different from bB aA). This lapse is why this is a comment and not an answer. $\endgroup$
    – kaine
    Feb 27, 2013 at 22:33

2 Answers 2

1
$\begingroup$

Hint: Start by imagining that the marbles are numbered, so are all distinguishable. If there are $n$ marbles in each bag, you can line the ones in the first bag up and there are $n!$ ways to match up the marbles from the second bag. Then if you have four blue marbles that are indistinguishable in the first bag, there are $24$ ways that get collapsed to $1$

$\endgroup$
3
  • $\begingroup$ That's what I thought at first, too; but the problem is that there are sets of indistinguishable marbles in both bags; and some of the $n!$ permutations of the matching may coincide with permutations among those sets and others may not. $\endgroup$
    – joriki
    Feb 27, 2013 at 21:24
  • $\begingroup$ @joriki: Good point. It will be more complicated. $\endgroup$ Feb 27, 2013 at 21:38
  • $\begingroup$ Yes, I have it that far - if I assume that all the marbles in one of the two bags is unique, I can find the number of permutations of the marbles in the second bag: N!/(n1!n2!n3!), N=total marbles, n1=marbles of color 1, etc... But as @joriki mentioned, there will be repeated permutations as the marbles in one bag are not unique. $\endgroup$
    – Albeit
    Feb 27, 2013 at 21:41
0
$\begingroup$

This explanation will look at the cases of: a) one bag contains 2 colors and the other contains and arbitrary number of colors; b) one bag contains 3 colors and the other contains arbitrary number; and c) each bag contains arbitrary numbers.

For every part below there are two bags containing n marbles. $n_{i,j}$ refers to the number of marbles of the jth color in the ith bag. $c_i$ is the number of different colors in bag i.

If anyone is willing to help confirm accuracy of this, i would be very appreciative as I've derived all of this using the referenced question as the only guide and I don't use combinatorics much.

a) As long as $c_1=2$ (as with the question's example), this problem is equivalent to just picking $n_{1,1}$ balls from the second bag.

number of combinations without repetition with limited supply

The above question helps explain how to find the number of combinations of $n_{1,1}$ marbles from bag two. Essentially you analyze the following polynomial for the coefficients:

$$P = \prod_{j=1}^{c_2}{\sum_{k=0}^{n_{2,j}}x^k}$$

For the question example:

$$P=(1+x)(1+x)(1+x+x^2+x^3) = 1+3x+4x^2+4x^3+3x^4+x^5$$

and the answer is 4 because the coefficient of $x^2$ is 4. This makes sense as the potential cases can be described as the colors paired with blue (black/black, red/black, white/black, and red/white).

b) The problem becomes more complicated when each bag contains more than 2 types of marbles. For the case of 3 colors in bag 1, the simular case requires that one consider both an x and a y. Define a polynomial:

$$F = \prod_{j=1}^{c_2}{\sum_{k=0}^{n_{2,j}}(\sum_{l=0}^{k} x^ly^{k-l})}$$

Convert it into an expanded form and note that the coefficient of $x^{n_{1,1}}y^{n_{1,2}}$ is the number of relevant combinations.

For examples, if $n=5$, $c_1=3$, $c_2=3$, $n_{2,1}=2$, $n_{2,2}=2$, $n_{2,3}=1$ then:

$$F=(1+x+y+x^2+x*y+y^2)^2*(1+x+y)$$ $$F=x^5+3 x^4 y+3 x^4+5 x^3 y^2+8 x^3 y+5 x^3+5 x^2 y^3+11 x^2 y^2+11 x^2 y+5 x^2+3 x y^4+8 x y^3+11 x y^2+8 x y+3 x+y^5+3 y^4+5 y^3+5 y^2+3 y+1 $$

If bag 2 contains 2 black, 2 red, and 1 green (for instance) there will be 11 combinations.

c) For the final case of an arbitrary number of colors in each bag, i am not sure how to write the notation. Each component in bag 1 must be assigned a letter (for instance x or y in the above examples). Define $x^ay^bz^c...$ as the state in which a are paired with color x and b are paired with color y and c are paired with color z etc. You can then define a state polynomial f such that it is the sum of all probablistic states that are possible for a particular color from bag 2 (aka f = xz+yz+zz+xy+y^2 means that the color in question can be paired with 1x and 1z, 1y and 1z, 2zs, 1x and 1y, or 2ys but 2xs are impossible. All states included in f must be mutually exclusive. Multipling all of these f state polynomials together will form an overall state polynomial F simular to those seen above. By this solution, a 1 in the f state polynomial would indicate that none of that color are chosen so would not appear in any problem where all marbles are paired up.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .