Why is this combinatoric solution not correct?

Question

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!

Answer 1

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

Answer 2

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.

Answer 3

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.