[Math] Formula for Combinations With Replacement

combinationscombinatorics

I understand how combinations and permutations work (without replacement). I also see why a permutation of $n$ elements ordered $k$ at a time (with replacement) is equal to $n^{k}$. Through some browsing I've found that the number of combinations with replacement of $n$ items taken $k$ at a time can be expressed as $(\binom{n}{k})$ [this "double" set of parentheses is the notation developed by Richard Stanley to convey the idea of combinations with replacement].

Alternatively, $(\binom{n}{k})$ = $\binom{n+k-1}{k}$. This is more familiar notation. Unfortunately, I have not found a clear explanation as to why the above formula applies to the combinations with replacement. Could anyone be so kind to explain how this formula was developed?

Best Answer

Assume the question is about buying 6 cans of soda pop from 4 brands of soda. Of course, there is more than 6 cans of soda for each brand. The number of different combinations is $\binom{4+6-1}{6} = 84. $

Think of it this way: If you wanted 2 cans of soda pop from the 4 brands, the second can of pop can be the same as the first one. Therefore, the reason it is $\binom{5}{2}$ is because one of the options out of the 5 is "duplicate" pop. If it is $\binom{4}{2}$, it would not be combination with replacement.

Therefore, in $\binom{4+6-1}{6} $, the 6-1 pop (or k-1) is the "duplicate" pop meaning it can be one of the pop that has been picked.

Related Question