0

I've been struggling with this for a while: I have 12 distinguishable balls and 10 distinguishable boxes. I need to find the probability that there are no cases in which there are boxes with exactly 4 balls in a box. So I thought of going at this way: taking all the possibilities of distribution and subtracting the amount of distributions that there 4 balls in a box. Starting with : $10^{12} - ({}_{10}C_3)({}_{12}C_4)({}_8C_4)({}_4C_4)$ which is the case that any 3 boxes have 4 in them. Couldn't find a way to calculate the rest. (And in the end dividing by $10^{12}$).

Will Orrick
  • 18,220
EMA
  • 3
  • Where does this $10^{12}$ come from? Can a ball be in more than one box? – kimchi lover Nov 19 '19 at 18:47
  • I might be wrong, but I can choose 1 of 10 distinguishable boxes for 12 different balls. So each time I'm choosing a box. And the number of boxes doesn't change. So I'm choosing 1 of 10 boxes 12 times (10^12). – EMA Nov 19 '19 at 18:51

2 Answers2

1

You have 12 balls, so if there is a box with 4 balls:

  • A) you can have 1 box with 4 balls and the other 8 balls in the other 9 boxes
  • B) you can have 2 boxes with 4 balls each and then the remaining 4 balls in the other 8 balls
  • C) you can have 3 boxes with 4 balls each

If you manage to write in how many ways each situation A, B and C can happen, then you can use the principle of inclusion-exclusion to find the final number you have to divide by $10^{12}$.

RGS
  • 9,719
  • Yeah, I realized that. My difficulty was another: if for ex: 2 boxes with 4 balls than the calculation for that would start with (10C2)(12C4)(8C4), but then the rest of the 4 balls can be devided in 8^4 ways. And a few of those ways can also be that 1 of the 8 boxes has 4 balls in it. It gets more complicated when 1 box has 4, so: (10C1)(12C4), the can be distributed in 9^8 ways, how do I subtract the number of ways that there are 4 balls in a those ways in a 1 or more boxes? – EMA Nov 19 '19 at 18:56
1

This is similar to the answer of RGS, but I thought you might need a bit more to get going.

Let $E_i$, $1\le i\le10$ be the event that box $i$ contains exactly four balls. The number of outcomes in $E_i$ is $\binom{12}{4}\cdot9^8$.

The principle of inclusion-exclusion implies that the number of outcomes in which no box contains exactly four balls is $$ \begin{aligned} &10^{12}-\sum_{i=1}^{10}\lvert E_i\rvert+\sum_{1\le i<j\le10}\lvert E_i\cap E_j\rvert-\sum_{1\le i<j<k\le10}\lvert E_i\cap E_j\cap E_k\rvert\\ &\quad=10^{12}-10\lvert E_1\rvert+\binom{10}{2}\lvert E_1\cap E_2\rvert-\binom{10}{3}\lvert E_1\cap E_2\cap E_3\rvert. \end{aligned} $$ This is how you handle the issue raised in your comment to RGS's answer. The principle of inclusion-exclusion automatically compensates for all double or triple subtraction. If you are unfamiliar with this, you should be able to find a good explanation in any combinatorics textbook.

Will Orrick
  • 18,220