2
$\begingroup$

I am terrible at combinatorics so any and all help would be appreciated.

20 identical balls are put into 10 distinct boxes so that at most 3 boxes are empty. In how many ways can this be done?

Thanks

$\endgroup$
  • $\begingroup$ Starting a question with "I am terrible at xxx..." is just shorthand for "I haven't tried to solve this problem". How many ways are there of placing 20 balls into 10 boxes with no boxes empty? If one is empty, this is placing 20 balls into 9 boxes with no boxes empty. Etc. $\endgroup$ – rogerl Dec 28 '14 at 1:30
  • 3
    $\begingroup$ Sorry to shatter your illusion and knock you off your high horse but it just so happens that there are people who are so unfamiliar with a topic that they cannot solve a problem without another person's aid despite how long they attempt the problem. But thanks for your incredibly useful underhanded condescension. $\endgroup$ – A is for Ambition Dec 28 '14 at 1:32
  • $\begingroup$ Anyway, I wanted to solve this problem by breaking it up into several cases: 0 boxes empty, 1 empty, 2 empty, and 3 empty. In the case with 0 boxes empty, would it be 19 choose 9? $\endgroup$ – A is for Ambition Dec 28 '14 at 1:34
  • $\begingroup$ Yes, that's the right approach. You have to remember to take into account how many ways there are of selecting nine boxes of 10, and so forth. $\endgroup$ – rogerl Dec 28 '14 at 1:34
  • $\begingroup$ If there are zero boxes empty, then you must put one ball in each box, and then distribute the remaining ten freely among all ten boxes. $\endgroup$ – rogerl Dec 28 '14 at 1:35
5
$\begingroup$

We can split this into $4$ cases based on the number of empty boxes, and use stars and bars for each case.


Case 1: No empty boxes.

We place $1$ ball in each box, and we imagine $9$ dividers and the remaining $10$ balls, so the number of possible ways to arrange the $19$ objects is $$\binom{19}{9}$$

Case 2: One empty box.

There are $10$ ways to choose the empty box. We place $1$ ball in each of $9$ boxes, and imagine $8$ dividers with the remaining $11$ balls, so the number of ways to arrange the $19$ objects is $$10\binom{19}{8}$$

Case 3: Two empty boxes.

There are $\binom{10}{2}=45$ ways to choose which boxes are empty. We place $1$ ball in each of $8$ boxes, and imagine $7$ dividers with the remaining $12$ balls, which gives $$45\binom{19}{7}$$

Case 4: Three empty boxes.

There are $\binom{10}{3}=120$ ways to choose which boxes are empty. We place $1$ ball in each of $7$ boxes, and imagine $6$ dividers with the remaining $13$ balls, which gives $$120\binom{19}{6}$$


Our final answer is

$$120\binom{19}{6}+45\binom{19}{7}+10\binom{19}{8}+\binom{19}{9}=\boxed{6371498}$$

$\endgroup$
  • $\begingroup$ For each case where there IS an empty box, shouldn't you multiply by $\dbinom{10}{n}$, where $n$ is the number of boxes you want to be empty? So for example, if there is one box empty, there would be $\dbinom{10}{1}$$\dbinom{19}{8}$ because there the boxes are distinct, so it matters which ones are selected to be empty. $\endgroup$ – A is for Ambition Dec 28 '14 at 1:40
  • $\begingroup$ @user155812 You're right, I've fixed it :) $\endgroup$ – Zubin Mukerjee Dec 28 '14 at 1:41
  • $\begingroup$ @user155812 in fact, it may help to understand the generalization to correct it to "for each case you multiply by $\binom{10}{n}$ where $n$ is the number of boxes you want to be empty" since we could have multiplied by $\binom{10}{0}=1$ in the case of zero empty boxes. $\endgroup$ – JMoravitz Dec 28 '14 at 1:44
  • $\begingroup$ Yes, thank you for your response Zubin. This is the answer I had gotten initially, but my lack of confidence combined with the fact that my classmates had gotten another answer made me unsure. $\endgroup$ – A is for Ambition Dec 28 '14 at 1:45
1
$\begingroup$

Hint: Can you do the case where no boxes are empty? That is a standard stars and bars. Then pick $9,8,7$ of the boxes (how many ways each?) and do the case where no boxes are empty. Add them up.

$\endgroup$
  • $\begingroup$ In the case with no empty boxes, would it be 19 choose 9? If it is, then I think I'm on the right track. $\endgroup$ – A is for Ambition Dec 28 '14 at 1:35
  • $\begingroup$ Furthermore, would the case with 1 box empty be $\dbinom{10}{1}$$\dbinom{19}{8}$? $\endgroup$ – A is for Ambition Dec 28 '14 at 1:37
  • 1
    $\begingroup$ Yes $19 \choose 9$ is the case where you do not allow any empty boxes. Your second is correct as well-$10 \choose 1$ picks the empty box and $19\choose 8$ puts the balls in the rest with no empties. $\endgroup$ – Ross Millikan Dec 28 '14 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.