1
$\begingroup$

In how many ways can we place 10 identical red balls (R) and 10 identical blue balls (B) into 4 distinct urns if each urn has at least 1 ball?

My attempt: Put the minimum number of balls into each urn:

case 1: R R R R (4C0, or 4 choose 0) ways to place 4 red balls, remaining 6R balls can be placed in 4 urns in (6+4-1)C(4-1) or (9 choose 3) ways, and 10B can be placed in (10+4-1)C(4-1) or (13 choose 3) ways, then total ways for this case 4C0*9C3*13C3 = 1*84*286 = 24024

case 2: B R R R, R B R R , etc, total of 4C1 ways to have 1 blue ball and 3 red ones, then for remaining 7R and 9B - 4C1*10C3*12C3 = 4*120*220 = 105600

case 3: B B R R , B R B R etc - following same logic 4C2*11C3*11C3 = 163350

case 4: 4C3*12C3*10C3 = 105600

case 5: 4C4*13C3*9C3 = 24024

Total ways = 24024+105600+163350+105600+24024 = 422598 However, the answer doesn't seem to be correct. What am I doing wrong?

$\endgroup$
  • 1
    $\begingroup$ Are the urns numbered? i.e. is B R R R really different from R B R R? If they are not ordered I would start with looking at how many ways there are to put 20 balls into 4 urns such that none is empty. This can be looked up as partitions of size 4 i.e. there are 64 such partitions. e.g. 6+6+4+4 Then for each partition one can see in how many ways one can fill urns with exactly 6,6,4,4 balls, which seems easier. $\endgroup$ – Rene Recktenwald Jun 4 at 10:38
  • $\begingroup$ maybe you've got to work it out first without the 1-ball constraint, then subtract all the combinations with zero in any pot, possibly remembering the inclusion exclusion principle to avoid double deducting $\endgroup$ – Cato Jun 4 at 10:56
  • 1
    $\begingroup$ Look up "Stars and Bars" for a general approach to the problem of counting the red ball arrangements (or the blue ball arrangements), with or without the restriction that every box has at least one ball. Then figure out how to combine those values for the problem at hand -- you'll also need a little bit of inclusion-exclusion, I think. $\endgroup$ – Ned Jun 4 at 13:07
3
$\begingroup$

By the complement rule, the answer = U-L, where:
U is the total number of ways 10 identical red balls (R) and 10 identical blue balls (B) can be placed into 4 distinct urns without constraints
$U={10+4-1 \choose 4-1}^2=81796$
L is number of ways with 1 or more urns having no balls
To find L, let's use inclusion-exclusion principle. Let set A be the set of all distributions of 10 red balls and 10 blue balls in urns 1,2 and 3. Set B is the set of all distributions of 10 red balls and 10 blue balls in urns 2,3 and 4; set C is the set of all distributions of 10 red balls and 10 blue balls in urns 1,2 and 4; set D is the set of all distributions of 10 red balls and 10 blue balls in urns 1,3 and 4. Then $L = A\cup B \cup C\cup D$ will be the set of all distributions in which at least one urn is left empty. By inclusion-exclusion
$L = |A\cup B \cup C\cup D| = |A|+|B|+|C|+|D|-(|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|) + (|A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D|) - |A \cap B \cap C \cap D|$
$|A| = |B|=|C|=|D|$ - number of ways 10 identical red balls and 10 identical blue balls can be placed into 3 distinct urns
$|A\cap B|=|A\cap C|=|A\cap D|=|B\cap C|=|B\cap D|=|C\cap D|$ - number of ways 10 identical red balls and 10 identical blue balls can be placed into 2 distinct urns
$|A \cap B \cap C|=|A \cap B \cap D|=|A \cap C \cap D|=|B \cap C \cap D|$ - number of ways 10 identical red balls and 10 identical blue balls can be placed into 1 urn
$|A \cap B \cap C \cap D|$ case when all urns are empty - not possible, therefore zero
$|A| = {10+3-1 \choose 3-1}^2=4356$
$|A\cap B|={10+2-1 \choose 2-1}^2=121$
$|A \cap B \cap C|={10+1-1 \choose 1-1}^2=1$
$L=4356*4 - 121*6 +4=17424-726+4=16702$
The ANSWER = $\boxed{U-L = 81796-16702=65094}$

$\endgroup$
1
$\begingroup$

When you do a question with the wording "at least" you almost always approaching it using the $1-$ not $P(A)$ method, because otherwise you are often likely to double count or miscount stuff.

For example in the way you approached the question, you have over counted in your case two. The reason is that if I put two red balls, with the four urns already having $B R B B$, they are fundamentally the same if I put them in the first urn and then the third urn compared to if I put them in the third urn and then the first urn. It is however different if I put one in he second urn and the other in the third urn.

This is because the ordering of the urn is taken care of at the step when you made a distinction between $B R B B$ as opposed to $R B B B$, then after that distinction, the three blue urn are no longer distinct. So placing a red ball in the first blue urn is no different to placing in the third blue urn for example.

Using the other method, you calculate the total number of way of placing the balls, then subtract all the ways with 1 or more urn having no balls. Then you should get the right answer.

$\endgroup$
  • $\begingroup$ Thank you. Following your suggestion, the answer should be the total number of ways to put 10 identical red balls and 10 identical blue balls into 4 distinct urns minus number of combinations with 1 urn empty minus number of combinations with 2 urns empty minus number of combinations with 3 urns empty, correct? Continued in next comment $\endgroup$ – Alexander Arefolov Jun 9 at 20:39
  • $\begingroup$ Total number of ways to put 10 identical red balls and 10 identical blue balls into 4 distinct urns without any constrains is ((10+4-1)C(4-1))^2 or (13 choose 3) squared = 81796 (I know this part is correct). Number of ways to have 1 urn empty should be (4C3)*((10+3-1)C(3-1))^2 : (4 choose 3) ways to choose one empty bin or 3 full bins times number of ways to fill 3 distinct bins with 10 identical red and 10 identical blue balls which should be (10+3-1)C(3-1)^2 or (12 choose 2) squared = 4*66^2=17424. Continued in next comment $\endgroup$ – Alexander Arefolov Jun 9 at 20:40
  • $\begingroup$ For 2 urns with no balls scenario - (4 C 2)*((10+2-1)C(2-1))^2 = 6* (11 choose 1)^2 = 6*121=726. For 3 urns with no balls: (4 C 1)*((10+1-1)C(1-1))^2 = 4. The answer then should be 81796 - (17424+726+4)= 63642. However, this answer still does not seem to be correct! $\endgroup$ – Alexander Arefolov Jun 9 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.