1
$\begingroup$

There is a collection of balls in three colours - red, yellow and blue -- and there are as many of each colour as we could want. There are four labelled boxes in order. You want to choose 10 balls and share them between the four boxes. It matters how many of each colour each box gets, but it doesn't matter what order they are in within the box. It does matter what order the boxes are in. It's ok to have no balls in a particular box, and it's ok to have no balls of a particular colour in any box.

For clarification, the following two arrangements are not different:

[RRBY][YYY][RBB][] & [RYBR][YYY][BRB][]

and the following arrangements are different:

[RRBY][YYY][RBB][] & [RRBY][][BRB][YYY]

$\endgroup$
2
$\begingroup$

This can be answered with a modification of the "stars and bars" method, though I prefer to use my own symbols.

Since the order of the colours within the boxes doesn't matter, we can choose them always to be in a predefined order of Red, Yellow, Blue. Taking the boxes and the colours within them in turn, this gives us 12 different categories, each of which can have any number of balls (including none), and the balls within each category are identical to each other.

Imagine taking each of these 12 categories in order, and moving along them. At any moment, you can put a new ball in this category (box-colour combination) or you can move to the next category. All-up there have to be 10 ball-putting actions, and 11 category-switching actions. You could represent the ball-putting actions as a small circle oooooooooo and the category-switching actions as an arrowhead >>>>>>>>>>>.

For example, the choice-allocation of [RRYB][][RBB][YYY] would be oo>o>o>>>>o>>oo>>ooo>.

With 10 balls and 11 arrowheads, there are 21 symbols in total, and 10 of them need to be chosen to be balls.

Thus in total we have ${{21}\choose{10}} = 352\ 716$ ways to choose and allocate.

$\endgroup$
1
$\begingroup$

A simpler view, but essentially @DavidButlerUofA's, is to say you are solving for non-negative, integer $x_{i c}$, where $i$ is the box and $c$ is the color:

$\begin{align} \sum_{\substack{1 \le i \le 4 \\ c \in \{R, Y, B\}}} x_{i c} = 10 \end{align}$

There are $4 \cdot 3 = 12$ variables in all, standard stars-and-bars tells you there are

$$\binom{12 + 10 - 1}{12 - 1} = \binom{21}{11}$$

ways to do this.

$\endgroup$
  • 1
    $\begingroup$ Simpler only if you happen to remember the formula for non-negative solutions to integer equations, which I always fail to remember. ;) (Still gave you a +1) $\endgroup$ – DavidButlerUofA Oct 19 '15 at 11:16
  • $\begingroup$ @DavidButlerUofA, that's why I mention stars and bars (no, I don't remember it most of the time either, so I have that argument handy). $\endgroup$ – vonbrand Oct 19 '15 at 11:20

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.