Combination with repetitions.

The formula for computing a k-combination with repetitions from n elements is: $$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}$$

I would like if someone can give me a simple basic proof that a beginner can understand easily.

Solution 1:

This problem comes by many names - stars and stripes, balls and urns - it's basically a question of how to distribute $n$ objects (call them "balls") into $k$ categories (call them "urns"). We can think of it as follows.

Take $n$ balls and $k-1$ dividers. If a ball falls between two dividers, it goes into the corresponding urn. If there's nothing between two dividers, then there's nothing in the corresponding urn. Let's look at this with a concrete example.

I want to distribute $5$ balls into $3$ urns. As before, take $5$ balls and $2$ dividers. Visually:

|ooo|oo

In this order, we'd have nothing in the first urn, three in the second urn and two balls in the third urn. The question then is how many ways can we arrange these 5 balls and two dividers? Clearly: $\dfrac{(5+3-1)!}{5!(3-1)!} = \displaystyle {7 \choose 2} = {7 \choose 5}$.

We have that there are $\dfrac{(n+(k-1))!}{(k-1)! n!}$ the $n$ balls and $k-1$ dividers (since the balls aren't distinct from each other and the dividers aren't distinct from each other). Notice that this is equal to $\displaystyle {n+k-1 \choose k-1} = {n + k - 1 \choose n}$.

Solution 2:

OK, suppose I draw (with replacement) $k$ items from the $n$, and mark them down on a scoresheet that looks like this, by putting an X in the appropriate column each time I draw an item.

The result will be $k$ Xs, separated by ($n-1$) vertical bars. Counting the Xs and the vertical bars together is $k+n-1$ items. And what I've drawn is entirely determined by which of those $k+n-1$ items are the Xs.

This is clearly $\binom{k+n-1}{k}$.