In how many ways can I distribute 5 distinguishable balls into 4 distinguishable boxes such that no box is left empty.

Question

So what I think is the way to solve this question is to first count the total number of ways of putting all the balls into boxes such that the restriction isn't satisfied (i.e. the total number of ways of putting the balls into the boxes). Then using the inclusion-exclusion principle for situations where the boxes are empty.

I think the number of total ways that you can distribute them would be $4^5$ but I'm unsure how to do the second part of the question.

Answer 1

One box will have two balls. Choose which box that will be, choose two balls to put in it, then put one ball in each of the remaining boxes.

$$\binom{4}{1}\binom{5}{2}\times 3!=4\times 10\times 6=240$$

Answer 2

Choose which two balls are to be paired, $\binom{5}{2}=10$, and then arrange the four objects, $4!=24$, for a total of $240$.

Answer 3

Your first part is correct. The number of the total ways is $4^5$.

Then you might consider the in-exclusion principle: $A_1$: $Box_1$ is empty; $A_2$: $Box_2$ is empty; $A_3$: $Box_3$ is empty; $A_4$: $Box_4$ is empty.

Use the same method that you got the number of total ways. For each of these cases, distributing $5$ distinguishable balls to $3$ distinguishable boxes, number of ways is $3^5$. $\binom{4}{1}$ shows it has $4$ cases.

$\vert A_1 \bigcap A_2\vert$ (Both Box 1 and Box 2 are empty) $= 2^5$. $\binom{4}{2}$ (from $A_1$ - $A_4$, choose $2$) shows how many cases in this situation.

$\vert A_1 \bigcap A_2 \bigcap A_3\vert$ (Boxes 1,2,3 are empty) $= 1^5$. $\binom{4}{3}$ cases.

$\vert A_1 \bigcap A_2 \bigcap A_3 \bigcap A_4 \vert$ (Boxes 1,2,3,4 are empty)= $0^5$. $\binom{4}{4}$ case.

Then apply inclusion-exclusion principle, $\vert A_1 \bigcup A_2 \bigcup A_3 \bigcup A_4 \vert$(at least one box is empty) $$=\sum_{k=1}^4 (-1)^{k+1}(4-k)^5 \binom{4}{k}$$

Finally, use the total number $4^5$ minus the number we got from the last step, then we get the number of ways that no box is empty.

To be honest, this method is much more complicated than other approaches. However, I guess you might want to generalise it to distribute $r$ distinguishable balls into $n$ distinguishable boxes(?) Then it definitely should be a good way to think about this question.