I recently came across this question in my textbook:

In how many ways can you distribute $3 ~\text{blue},~ 4~ \text{white}$ and $2~ \text{red}$ balls be distributed into $4$ distinct boxes?

My first thought (and in fact the suggested solution in my textbook) was to apply the principle of Stars and Bars to each of the Colorado and take their composite. The answer would evaluate to $\binom 63\cdot\binom 73\cdot\binom 53 = 7000$, an agreeable number.

However, I figured a more ‘organic’ method would be to derive a more general Stars and Bars for multiple types of objects. The way I went about this was to paraphrase this evaluation as an arrangement of $n-1$ bars and $r_1$ of some object, $r_2$ of another $\dots$, $r_k$ of a $k^{th}$ kind. The number of distinct arrangements of these elements would be $$(n-1+r_1+r_2\dots r_k)!\over (n-1)!r_1!r_2!\dots r_k!$$ or if we were to write the total number of objects $r_i$ as $r$ we have the more shorthand notation $$(n+r-1)!\over (n-1)!\displaystyle\prod_{i=1}^k r_i!$$

But, using this principle on this problem we have $$12!\over 3!3!4!2!$$ which at first glance looks extraordinarily large. In fact it evaluates to over $277000$ which is conceivably less agreeable than $7000$. (Please don’t question the language of “agreeable”).

What is wrong with this approach? (Or is it the earlier approach that is in fact incorrect?)

  • 1
    $\begingroup$ Be careful. An arrangement where in the first box you have a red ball then a blue ball and then the rest of the balls distributed somehow among the remaining boxes should be considered the same as an arrangement where in the first box you have a blue ball then a red ball and the rest of the balls distributed in the same way. Order within a box should not matter, but according to your attempt you made it so that it did matter. $\endgroup$ – JMoravitz Nov 25 '19 at 15:49
  • 1
    $\begingroup$ Whether or not you decide that order within a box matters will determine which of the answers you get. Order within a box not mattering giving you the earlier result. Order within a box mattering giving you the later result. Both are correct depending on what interpretation of the problem you are using, but again, it is far more common to use the first interpretation. $\endgroup$ – JMoravitz Nov 25 '19 at 15:52

Your method is almost correct, but you are over-counting some cases. Basically, you choose 9 balls and 3 bars to distribute, with the bars dividing the balls into 4 boxes. This is correct. You then divide by 3,2,3 and 4 factorial to account for the indistinguishability of the balls and bars. However, you neglect to consider that rearrangements within groups also give the same case. For example, consider the following:

BW | RWB | WB | WW

In group 1, whether you wrote BW or WB, doesn’t actually change the groups made. Same with groups 2 and 3. However, it is very hard using this method to eliminate the overcounting, since the group size can vary. The answer of 277000 is correct if the problem asked that the order of colors within the bucket matters, say if it was a line and not a bucket.


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.