Online Course Discussion Forum

Combinatorics Chapter 5, Example Question 5.6 (1 Year Self Paced Bundle)

 
 
Picture of Dr. Kevin Wang
Re: Combinatorics Chapter 5, Example Question 5.6 (1 Year Self Paced Bundle)
by Dr. Kevin Wang - Monday, May 1, 2023, 11:33 PM
 

This is in the Math Challenge II-B Combinatorics textbook.

The question: Suppose you have $10$ identical balls.  How many ways are there to put them in $7$ numbered boxes so that at least one of the boxes gets at least $4$ balls?

First of all, the balls are identical, and the boxes are numbered (which means distinguished), so we do not need to worry about rearrangement of the balls or boxes.  Thus, the $7!$ in your solution is not needed.

So you can pick a box to contain the $4$ balls first.  That's $7$ choices, no problem.

Then you place the remaining $6$ balls into the $7$ boxes.  This is a Stars and Bars problem, so you can get $\binom{12}{6}$ (not $\binom{12}{5}$, be careful about that).

So what's still wrong?  There is a possibility that we got $2$ boxes with at least $4$ balls each.  This case is overcounted, and need to be subtracted. To count this case, place $4$ balls each into two of the boxes, $\binom{7}{2}$, and then use Stars and Bars for the remaining $2$ balls, $\binom{8}{2}$.  Therefore the final answer would be

$$ 7\binom{12}{6} - \binom{7}{2}\binom{8}{2}.$$

One more note: whenever you see the phrase "at least", consider using complementary counting, or in some more complex cases, PIE.