0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ You must have. Even if you allow for empty boxes, you cannot get more than $4^6=4096$ ways. The overcounting comes from this: for example, if the colors are R(ed), O(range), Y(ellow), G(reen), B(lue), P(urple), then the grouping where R,O,Y are in the same box but G, B, P are separate is calculated (as it should be) $4!$ times, but then the grouping where $R,O,Y$ are in the same box but $B,G,P$ are separate are calculated $4!$ times again, even though those are the same ways as before. $\endgroup$
    – user700480
    Apr 11, 2021 at 19:20
  • 1
    $\begingroup$ The solution of the problem is $4!{6\brace4} $ where the last symbol stays for Stirling number of the second kind. $\endgroup$
    – user
    Apr 11, 2021 at 19:20
  • $\begingroup$ It's been like 6 years since I've thought about Stirling numbers, yikes! thanks for the help friends $\endgroup$
    – oshill
    Apr 11, 2021 at 19:38

2 Answers 2

Reset to default
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Right, so reminding myself how to construct the choice function I realized I overlooked the implicit ordering attached to it. Thanks! $\endgroup$
    – oshill
    Apr 11, 2021 at 19:45
1
$\begingroup$

Leaving out Stirling numbers of the second kind, (which needs that you should have a table of such numbers), expanding on your approach, all that is needed is to multiply each of your terms by another multinomial coefficient that counts how the two patterns can be permuted between boxes, thus

$\dbinom{6}{3,1,1,1}\dbinom{4}{1,3} +\dbinom{6}{2,2,1,1}\dbinom{4}{2,2} = 1560$

This can be done mechanically even in half-sleep !

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .