1
$\begingroup$

One solution I heard for this problem is by choosing a cell, put 3 balls into it(10 options), and then distribute the rest of the balls between the rest of the cells, so the answer will be: $10 \cdot D(9,3)=10 \cdot \dbinom{11}{3}=1650$
But I think that this is double-counting.

I solved it this way:
Find the number of ways to distribute the balls such that 1 cell will contain exactly 3 balls, and then exclude the intersections such that 2 cells will contain exactly 3 balls:
$C_i-$ Cell number i contains exactly 3 balls.
$|C_1| +|C_2| + ... +|C_{10}|=D(9,3) \cdot 10 = 1650$
$|C_1\cap C_2| + ...+|C_9\cap C_{10}|=D(8,0)\cdot \dbinom{10}{2}=1 \cdot 45=45 $
Therefore the result is: $1650-45=1605$.
I would like to know if my solution is correct. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ You are almost correct. You should actually have subtracted $45$ twice. You actually double counted each time that you have two cells with three balls each and you wanted to count each of those zero times. Subtracting once is what you do for if you wanted to count each arrangement with at least one cell with three balls once each. $\endgroup$ – JMoravitz Oct 17 '17 at 14:14
  • $\begingroup$ A good sanity check here: there are ten different cells and exactly one of them will have three balls. Even without completing the multiplication principle argument, you should still be able to argue that your final answer then must be divisible by $10$. $\endgroup$ – JMoravitz Oct 17 '17 at 14:15
  • 2
    $\begingroup$ An alternative way to fix it. Recognize that among the $\binom{11}{3}$ ways to distribute the remaining three balls, nine of the ways is bad as all balls went to the same cell. Avoiding those, we have an answer of $10\cdot \left(\binom{11}{3}-9\right)=1560$ $\endgroup$ – JMoravitz Oct 17 '17 at 14:20
  • $\begingroup$ Aha! Got it, thank you! $\endgroup$ – sinex Oct 17 '17 at 15:59
  • $\begingroup$ I see that you have attempted to use the Principle of Inclusion-Exclusion, sometimes called the Difference rule. What you have counted is the cardinality of $C_1\cup C_2\cup \ldots \cup C_{10}$. This includes the cases that 2 cells each have 3 balls. Hence, you have missed out the last step after applying the Principle of Inclusion-Exclusion, which is to subtract $45$. $\endgroup$ – yh016 Oct 26 '17 at 8:47
1
$\begingroup$

Not sure I follow your calculation.

One way to do it: you either have $3+2+1=6$ or $3+1+1+1=6$. In the first case you must choose the $3$ cell ($10$ choices) then choose the $2$ cell ($9$ choices) and then choose the $1$ cell ($8$ choices ) so $720$ in this case. For the second you must choose the $3$ cell ($10$ choices) and then choose the three $1$ cells ($\binom 93= 84$ choices). Thus $840$ in this case.

Your final answer then is $$720+840=\boxed {1560}$$

$\endgroup$
  • $\begingroup$ Got it, Thanks! $\endgroup$ – sinex Oct 17 '17 at 16:04
  • $\begingroup$ No problem. Side note: The site prefers it if you accept an answer. If you solved it another way (say by repairing the error in your original method) then you can post that as your own solution and accept it (and I'd upvote it). $\endgroup$ – lulu Oct 17 '17 at 16:08

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.