2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Distinguishable boxes or not? For $5$ and $3$ we do not need machinery for either. $\endgroup$ – André Nicolas Feb 2 '14 at 18:44
  • $\begingroup$ 3 different and distinguishable boxes. $\endgroup$ – Gabriele Salvatori Feb 2 '14 at 18:46
  • 1
    $\begingroup$ If you want generality, it is standard Stars and Bars (see Wilipedia). The answer is $\binom{5-1}{3-1}$. $\endgroup$ – André Nicolas Feb 2 '14 at 18:49
  • $\begingroup$ @AndréNicolas Aren't the balls different? $\endgroup$ – Zafer Cesur Feb 2 '14 at 18:50
  • 1
    $\begingroup$ The balls are different if we specify they are different. The problem should specify. I have written out answers under each of the interpretations. $\endgroup$ – André Nicolas Feb 2 '14 at 19:04
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ If the boxes were indistinguishable, would the answer be $(3^5-3\cdot 2^5+3\cdot 1^5)/3!$? $\endgroup$ – Zafer Cesur Feb 2 '14 at 19:06
  • $\begingroup$ $S_5^{(3)}$ is indeed equal to $(3^5-3\cdot 2^5+3\cdot 1^5)/3!$ $\endgroup$ – Zafer Cesur Feb 2 '14 at 19:15
  • $\begingroup$ Yes, they are equal. $\endgroup$ – André Nicolas Feb 2 '14 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.