Find the number of distributions of eight distinct balls into three distinct boxes if at least two balls must go into each box.

93 Views Asked by At

This question is very similar to another question I posted, but this is really giving me trouble.

My attempt: There are 3 choices for the balls, but after that I'm lost. I thought $$3\left[\binom82 \binom62\binom44\right]$$ but for some reason this does not feel right at all.

Please help, and thank you!

2

There are 2 best solutions below

2
On BEST ANSWER

There are $2\binom{8}{4,2,2}$ ways to place $4$ balls in box1 and $2$ in box2 and box3.

There are $2\binom{8}{2,3,3}$ ways to place $2$ balls in box1 and $3$ in box2 and box3.

So we end up $$3\cdot2\binom{8}{4,2,2}+3\cdot2\binom{8}{2,3,3}$$possibilities.


edit:

My original answer is not correct (sorry). I reasoned that a split up like 1234|56|78 gives $2$ possibilities under the condition that box1 gets the balls 1,2,3,4. Then box2 can get the balls 5,6 or it can get the balls 7,8. That is correct on its own, but in the factor $\binom8{4,2,2}$ this split up is counted twice allready: as 1234|56|78 and as 1234|78|56. So factor $2$ in my original answer is redundant. The same story for the second term.

The correct answer is:$$3\binom{8}{4,2,2}+3\binom{8}{2,3,3}=3\cdot420+3\cdot560=2940$$

0
On

Here is a variation based upon exponential generating functions.

  • A selection of at least two distinct balls can be encoded as \begin{align*} \frac{x^2}{2!}+\frac{x^3}{3!}+\cdots=e^x-1-x \end{align*}

  • Since we have three boxes we consider \begin{align*} (e^x-1-x)^3\tag{1} \end{align*}

We denote with $[x^n]$ the coefficient of $x^n$ in a series.

Since we are looking for the number of placing $8$ distinct balls we consider the coefficient of $x^8$ in (1) and obtain with some help of Wolfram Alpha

\begin{align*} 8![x^8](e^x-1-x)^3=\color{blue}{2\,940} \end{align*}

Hint: You have just missed the case where three balls each are in two boxes. Respecting this case also you get \begin{align*} 3\left[\binom{8}{2}\binom{6}{2}\binom{4}{4}+\binom{8}{3}\binom{5}{3}\binom{2}{2}\right] &=3\left(28\cdot15\cdot1 +56\cdot 10\cdot 1\right)\\ &=3\left(420+560\right)\\ &=\color{blue}{2\,940} \end{align*}