In how many ways we can place 9 different balls in 3 different boxes such that in every box at least 2 balls are placed?

Question

In how many ways we can place $9$ different balls in $3$ different boxes such that in every box at least $2$ balls are placed?

Approach 1:

Let $x_1$, $x_2$, $x_3$ denote the number of balls in boxes $1$,$2$, and $3$ respectively. Now,solving $x_1+x_2+x_3 =9$ for $2≤x_1≤x_2≤x_3≤5$ ($5= 9-$(min of $x_1$) $-$ (min of $x_2$)), we get $(x_1,x_2,x_3) ≡ (2,2,5),(2,3,4),(3,3,3)$

Now, we have to divide $9$ objects in these groups and then distribute into boxes. So the required answer is $$\frac{9!}{2!2!5!}×\frac{1}{2!}×3! +\frac{9!}{2!3!4!}×3! + \frac{9!}{3!3!3!}×\frac{1}{3!}×3!$$ which simplifies to be $\boxed{11508}$. This is the correct answer.

Approach 2 (PIE):

At least $2$ $=$ all $-$ at most $1$. Now, considering $1$ box contains no ($0$) elements, the number of cases corresponding to that is ${3 \choose 1}×2^9$ and the number of cases when $2$ boxes contain no elements will be ${3 \choose 2}×1^9$. Now, number of cases when $1$ box contains only $1$ element is ${3 \choose 1}×{9 \choose 1}×2^8$ (I.e., number of ways to choose 1 box × number of ways to choose 1 ball × remaining distribution) and the number of cases when 2 boxes contain only 1 element is ${3 \choose 2}×{9 \choose 2}×1^7$ . So, using PIE, the required answer should be $$3^9 -({3 \choose 1}2^9 - {3 \choose 2}1^9) - ({3 \choose 1}{9 \choose 1}2^8 - {3 \choose 2}{9 \choose 2}1^7)$$ that is $11346$. This answer is wrong but the "closeness" of the answer to the correct one indicates that I have deducted some cases. Please point out my mistake in approach 2.

Answer 1

There are two small mistakes otherwise your work using the second approach is also correct. It should be -

$ \displaystyle \small 3^9 - \underbrace{\left[{3 \choose 1}2^9 - {3 \choose 2}1^9 \right]}_{\Large {(a)}} - \underbrace{\left[{3 \choose 1}{9 \choose 1} (2^8 - \color { blue } {2}) - \color { blue } {2} \cdot {3 \choose 2}{9 \choose 2}1^7 \right]}_{\Large (b)}$

Explanation on what I added in $ \color {blue} { \text {blue}}$ in $(b)$:

$1)$ Please note $2^8$ also includes two arrangements where one of the two boxes is empty but those are already counted in $(a)$. So we need to subtract those two arrangements.

$2)$ Please note when we choose two balls for two boxes, there are $2$ ways to place them in two boxes such that each box has one ball.

Answer 2

$\mathbf{\text{For Alternative Approach:}}$

Distinct balls into distinct boxes with restriction , then it is good time to use exponential generating functions , if each boxes will have at least two objects , then the e.g.f. of each boxes is equal to $$\bigg(\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}\bigg)$$

We restricted it with $x^5$ , because if each boxes will have at least $2$ ball , then a box can have at most $5$ balls , then find the coefficient of $x^9$ in the expansion of $$\bigg(\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}\bigg)^3$$ and multiply it by $9!$.

Then , $$9! \times \frac{137}{4320}= 11,508$$