How many ways to put balls into boxes

combinatorics

We have 6 differently colored balls and 4 boxes labelled 1 through 4. How many different ways can we fill the boxes using the 6 balls such that no box is left empty?

We can ignore the boxes for now, and consider grouping the balls into 4 different groups, which we can do $\dbinom{6}{3,1,1,1}+\dbinom{6}{2,2,1,1}=6\cdot 5\cdot 4+6\cdot5\cdot3\cdot2=120+180=300$ different ways. Then given one of these combinations of balls, there are $4!$ different ways to deposit them into the boxes, leaving a possible $300\cdot 4!=7200$ different ways. I am unsure of where I misplayed my cards here.

Best Answer

Labeling the colors $A,B,C,D,E,F$ for conciseness, and using an ordered list of sets of colors to represent how the boxes were filled with balls, consider the arrangement

$$ \{A, B, C\}, \{D\}, \{E\}, \{F\}. $$

You have counted this arrangement six times.

One way you counted it was by making the grouping $ \{A, B, C\}, \{D\}, \{E\}, \{F\} $ and putting these sets of balls in the boxes in exactly the order they are listed here (i.e., the identity permutation). Another way you counted it was by making the grouping $ \{A, B, C\}, \{E\}, \{D\}, \{F\} $ and swapping the middle two sets before putting the sets of balls in the boxes. The other four ways you counted this arrangement correspond to the other four permutations of the last three subsets.

Dividing by $6$ won't help, because you counted each of the groupings such as $ \{A, B\}, \{C, D\}, \{E\}, \{F\} $ exactly four times.


A correct count:

Each of the $\binom{6}{3,1,1,1} = 120$ groupings of the first kind can be distributed into boxes in $\binom 41 = 4$ different ways (choose which box gets the set of three, but keep the relative order of equal-sized sets the same). Each of the $\binom{6}{2,2,1,1} = 180$ groupings of the second kind can be distributed into boxes in $\binom 42 = 6$ different ways (choose which boxes get sets of two, etc.).

So that's a total of $$ 120 \cdot 4 + 180 \cdot 6 = 1560 $$ arrangements.

Note from the comments that $4!{6\brace4} = 24 \cdot 65 = 1560.$

Related Question