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.

Answer

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

Attribution
Source : Link , Question Author : Community , Answer Author : notes

Leave a Comment