1
$\begingroup$

I'm trying to solve the following problem:

Balls of the colors red, orange, yellow, green, blue, indigo, violet (7 colors, 1 ball per color) are placed into 4 different boxes A,B,C,D so that no box is empty. In how many ways can that be done?

I tried to solve this, and I can't figure out why my solution is wrong. My question is, why is my solution wrong?

What I did was the following:

$\binom{7}{1}\binom{4}{1}+\binom{6}{1}\binom{3}{1}+\binom{5}{1}\binom{2}{1}+\binom{4}{1}$

First picking one ball out of 7, combining the choice with 1 out of 4 possible boxes, then adding the number of ways to pick the next ball, 1 out of 6 remaining balls, to place in 1 out of 3 allowed boxes and so on..

Then I combined these choices with the placements of the remaining 3 balls (3 balls that can all have 4 different positions gives $4^3$ choices) and got:

$\left(\binom{7}{1}\binom{4}{1}+\binom{6}{1}\binom{3}{1}+\binom{5}{1}\binom{2}{1}+\binom{4}{1}\right)\times 4^3=60\times 64=3840$

According to the book, the right answer is 8400. Why is my solution wrong? Thanks!

$\endgroup$
  • 1
    $\begingroup$ I think you should just multiply instead of add in your first equation. Since placing the second ball produces not 'additional' possiblilities, but for each placements of the first ball, you can have those possiblilities for the second one, and so forth. Another approach would be havin $C(7,4)$ possibilities of drawing $4$ balls and then having $4!$ possibilities of arranging them. $\endgroup$ – flawr Dec 15 '14 at 21:56
  • 1
    $\begingroup$ And once you have done that, you count each valid configuration repeatedly. E.g. "violet to A, then blue to C, then red to B, then yellow to D, then the rest somehow" is the same as "violet to A, then red to B, then blue to C, then yellow to D, then the rest somehow", not to mention that the distinction between first four balls and "the rest" leads to even more repeated counting. $\endgroup$ – Hagen von Eitzen Dec 15 '14 at 21:59
  • $\begingroup$ I just found that by multiplying you will count many combinations twice, so that will not work either. $\endgroup$ – flawr Dec 15 '14 at 22:03
3
$\begingroup$

As the commenters have pointed out, your approach is incorrect in a couple of ways; for starters, you should be multiplying rather than adding, but then you are drastically overcounting.

You are trying to partition the seven balls into four nonempty boxes. The number of ways to partition $7$ things into $4$ nonempty sets is given by the Stirling number of the second kind, $\left\lbrace{7\atop 4}\right\rbrace = 350$. Here, however, the order of the sets is important (they are distinct), so you must multiply by $4!$; $350\cdot 4! = 8400$.

$\endgroup$
  • $\begingroup$ Very nice answer, thank you. $\endgroup$ – John Dec 15 '14 at 22:08
1
$\begingroup$

Three cases for the distribution:

  1. 4,1,1,1
  2. 3,2,1,1
  3. 2,2,2,1

Case 1: Pick the box that gets four balls ($4$) and pick the balls that go in there ($_7C_4$). Finally, pick the order of the remaining three balls in the last three boxes ($6$).

Case 2: Pick the box that gets three balls ($4$) then the one that gets two ($3$). Choose the balls that go into the three-box ($_7C_3$) and then the ones that go into the two-box ($_4C_2$). Choose which remaining ball goes in which remaining box ($2$).

Case 3: Pick the box that gets one ball ($4$) and choose which ball goes there ($7$). Then choose the two balls that go into the first remaining box ($_6C_2$), the second ($_4C_2$) and the last ($1$).

Calculating the combinations by multiplying the values in each case, and adding, gives $840 + 5040 + 2520 = 8400.$

One note on the wording of your initial solution:

First picking one ball out of 7, combining the choice with 1 out of 4 possible boxes, then adding the number of ways to pick the next ball, 1 out of 6 remaining balls, to place in 1 out of 3 allowed boxes and so on..

This suggests that you're already double-counting. If I put the red one in box A, then put the orange one in box B, I just as easily could have put the orange one in box B, then put the red one in box A. Exactly the same configuration, but counted twice.

For Case 1 above, let's say you choose the colors for $A,B,C,D$ in that order. This gives $7\cdot 6 \cdot 5 \cdot 4 = 840$ possibilities. When you put the remaining three balls into one of the boxes, you choose the box ($4$) but this creates a fourfold repetition of every combination. Any one of the balls that is in that full box could have instead been the first one put in. So, you have to divide by four: $840 \cdot 4 / 4 = 840.$

Accounting for the double counting in the other cases is similar.

$\endgroup$
  • $\begingroup$ Nice alternative solution, didn't even cross my mind to do it like that. $\endgroup$ – John Dec 15 '14 at 22:19
0
$\begingroup$

Hint: you can try the formula for k (distinguishable) urns and n (distinguishable) balls. At least on ball in every urn.

$$k!\cdot S_{n,k}=k!\cdot \frac{1}{k!}\sum_{î=0}^{k-j} {k \choose i }\cdot i^n$$

$S_{n,k}$ is a Stirling number of the second kind.

$\endgroup$

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.