# Counting problem: selecting $n$ objects among $k$ infinite collections.

Here's a counting question that got me thinking. Unfortunately, I couldn't get around it. Need help.

You are given $k$ distinct coloured boxes. In each box, lies infinite balls of the same colour as of the box. All the balls of a particular colour are exact copies. You are asked to choose $n$ balls from the whole collection. While making the selection, remember that you need to have $1$ ball of each colour at least. In how many total ways, can you make the selection?

Example. If there are 3 coloured boxes — red, green & blue — then there will be infinite red balls in the first (red) box, infinite green balls in second (green) box and so on...

Now you are asked to choose $5$ balls, then there is $6$ ways to do so.
r g b r r
r g b g g
r g b b b
r g b r g
r g b g b
r g b b r
(I hope I didn't missed any case in the example)

The first thing to notice about this question is that from the chosen $n$ balls, there are $k$ balls that are always the same, due to the requirement of at least on ball each being required - In effect, we are choosing combinations from only $n-k$ balls.

The next thing to note is that from this is that the combinations are unordered and repetition is allowed. There is a general formula for this case:

$$\binom{n + r -1}{r} = \frac{(n+r-1)!}{(n-1)! \cdot r!}$$

Where $n$ is the number of objects to choose from, $r$ is the amount of items we choose, $\binom{n}{k}$ the binomial coefficient and $x!$ the factorial of $x$. An explanation of the formula can be found under this link, near the bottom.

In our case, the $n$ in the formula is unfortunately your $k$, the amount of boxes, and $r$ is $n-k$. In effect:

$$\text{Amount of selections:} \binom{k + n-k - 1}{n-k} = \binom{n-1}{n-k}$$

Putting in $n = 5$ and $k = 3$, this does indeed come up to $6$.

• It seems like it boils down to Stars and Bars theorem with n being the Stars and k being the bars giving the distribution of atleast one ball in each box with ${n-1\choose k-1}$ again could be reduced to ${n-1\choose n-k}$. Jun 27, 2014 at 10:11
• Thanks for help. Although I couldn't derive the same at first go, but after spending some time on random data and pen-paper analysis, I did get the result. Besides that, any idea from where I could learn some more about combinatorics online? Jun 27, 2014 at 10:13
• @zibs.shirsh Have a look at the Wikipedia article about multisets, I gave in my answer.
– mvw
Jun 27, 2014 at 10:22
• @satishramanathan Looks like it, haven't seen this theorem before but it looks correct. As for the learning, I don't really have any resources on it, but a search with any engine about combinatorics should yield at least some good results. Jun 27, 2014 at 10:23
• @zibs.shirsh, check out Bogart's "Combinatorics through Guided Discovery" Jun 27, 2014 at 10:34

You have to take at least one ball from every box, that leaves $m = n - k$ balls out of $k$ boxes for free selection.

And indeed you start all your examples with the initial drawing of one ball from each box (prefix "rgb").

As user Alex pointed out, you seem to not differentiate the order how that happens. Then this process is similiar to $m$ draws from a $k$-multiset, which has this number of different choices:

$$\left(\left( \begin{matrix} k \\ m \end{matrix} \right)\right) = \binom{k+m-1}{m} = \binom{n-1}{n-k}$$

For your examples with $k = 3$ and $n = 5$ this gives $\binom{4}{2} = 6$ ways to do it.

• I think OP doesn't count rgbrg and rgbgr as two different ways, you did though.
– Alex
Jun 27, 2014 at 9:09
• rgbrg and rgbgr are the same - only selection matters, not the arrangement. Jun 27, 2014 at 10:18