[Math] Ways to put $5$ balls in $3$ boxes if each box must contain at least $1$ ball.

combinatoricsstirling-numbers

How many ways can you put $5$ balls in $3$ boxes if each box must contain at least one ball?

I've some doubts about this issue, I think the solution is related to the second kind of Stirling numbers but I cannot figure out the correct solution.

So, assuming that $\left\{n\atop k\right\}$ is the number of ways we can partition a set of $n$ objects into $k$ non-empty subsets, how can i consider all possible combinations that determine the subsets in order to solve the problem?

Best Answer

First we assume that the balls are indistinguishable.

Line up the $5$ balls like this $$ B\qquad B \qquad B \qquad B \qquad B$$ We will choose $2$ from the $4$ gaps between $B$'s to put a separator into. Then all $B$ up to the first separator go into the first box, all $B$'s between the two separators go into the second box, and the rest go into the third.

There are exactly as many ways to insert separators as there are ways to distribute the balls between the boxes. So there are $\binom{5-1}{3-1}$ ways to do the job.

Remark: The idea generalizes. Please see the Wikipedia article on Stars and Bars.

Next we assume the balls are distinguishable. We use Inclusion/Exclusion. There are $3^5$ ways to distribute the balls, with no restriction.

There are $2^5$ patterns in which the first box is empty, and the same number with the second empty, and the same with the third empty.

However, if we subtract $3\cdot 2^5$ from $3^5$, we have subtracted too many times the patterns in which two of the boxes are empty. So we need to add back $3\cdot 1^5$, giving count $3^5-3\cdot 2^5+3\cdot 1^5$.