There are six balls, colored red, orange, yellow, green, blue, and purple. There are also 3 boxes, numbered 1, 2, and 3. How many ways are there to put the balls in the boxes, such that each box has at least 1 ball?
I had 2 methods of doing the problem and got different answers.
-
Method 1: I pick a ball to put in box 1, then a ball to put in box 2, and a ball to put in box 3. There are $6\cdot5\cdot4$ ways to do that. Then, the three balls can be randomly put in the three boxes, giving $3^3$. Multiplying them together gives $6\cdot5\cdot4\cdot3^3=3240$ ways.
-
Method 2：I use complementary counting. There are $3^6$ ways to put the distinct balls into the distinct boxes (without any restrictions). Then, I subtract the ways to put the balls into 2 boxes: $3\cdot2^6$ for the $3$ ways to pick the two boxes, and $2^6$ ways to put the balls into the boxes. Then, I add the ways to put the balls into 1 box: $3\cdot1^6$ to pick a box and put all the balls in it. I get $3^6-3\cdot2^6+3\cdot1^6=540$ ways.
Which method, if any, is correct?
Best Answer
Your second method is correct.
Your first method overcounts. For instance, that method considers the following four to be distinct:
But they all result in the same configuration of balls in boxes, so they shouldn't be distinct. In fact, it overcounts so much that you find more than $3^6$ ways of doing it.