Online Course Discussion Forum

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

 
 
Picture of Maximus Sheng
Combinatorics Chapter 5, Example Question 5.6 (1 Year Self Paced Bundle)
by Maximus Sheng - Saturday, 29 April 2023, 11:57 AM
 

For this problem, I don’t understand why you would need to use PIE. There is a much easier way to do it without, but I got a different answer. 

Why does


(12 choose 5) * 7! * 7 not work?


12 choose 5 is for how many ways there are to choose 6 balls into 7 boxes

7! Is the amount of ways you can rearrange them, and 7 is how many ways there are to chose the 1st box.



 
Picture of Dr. Kevin Wang
Re: Combinatorics Chapter 5, Example Question 5.6 (1 Year Self Paced Bundle)
by Dr. Kevin Wang - Monday, 1 May 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.