# Formula for Combinations With Replacement

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?

http://www.mathsisfun.com/combinatorics/combinations-permutations.html

First result on Google for 'combinations and permutations'. They give an explanation that anyone should be able to understand.

• umm.. The first link on Google for "combinations with replacement" gives your answer. This seems to be an infinite recursion. – Pragy Agarwal Nov 27 '17 at 16:52
• Not so. Observe that I suggested a different search query to that. – user85798 Nov 27 '17 at 20:44
• Downvoting this link-only answer. – Richard Jun 5 '18 at 18:59

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.

I have been looking for the same answer and I finally found something I could understand and explain to my 10 year old.

Benjamin & Quinn 2003, p. 71 For example, if you have four types of donuts (n = 4) on a menu to choose from and you want three donuts (k = 3), the number of ways to choose the donuts with repetition can be calculated as

This result can be verified by listing all the 3-multisubsets of the set S = {1,2,3,4}. This is displayed in the following table.

No. 3-Multiset Eq. Solution 1 {1,1,1} [3,0,0,0]
2 {1,1,2} [2,1,0,0]
3 {1,1,3} [2,0,1,0]
4 {1,1,4} [2,0,0,1]
5 {1,2,2} [1,2,0,0]
6 {1,2,3} [1,1,1,0]
7 {1,2,4} [1,1,0,1]
8 {1,3,3} [1,0,2,0]
9 {1,3,4} [1,0,1,1]
10 {1,4,4} [1,0,0,2]
11 {2,2,2} [0,3,0,0]
12 {2,2,3} [0,2,1,0]
13 {2,2,4} [0,2,0,1]
14 {2,3,3} [0,1,2,0]
15 {2,3,4} [0,1,1,1]
16 {2,4,4} [0,1,0,2]
17 {3,3,3} [0,0,3,0]
18 {3,3,4} [0,0,2,1]
19 {3,4,4} [0,0,1,2]
20 {4,4,4} [0,0,0,3]

Considering a multiset with $$n$$ distinct types of objects and at least $$k$$ of each type, we are interested in counting the number of submultisets of size $$k$$. If we have $$x_i$$ elements of the $$i^{th}$$ type, then the number of such multiset corresponds to the number of non-negative integer solutions of $$x_1 + x_2 + \cdots x_n = k$$, and that is $$\binom{n+k-1}{k}$$. To see that this formulation makes sense, considering the example of submultisets of size 3 taken from the mutiset with 4 types provided by HKA, note that the sums of the entries in the square brackets, which count the number of repetitions of each type of element, all sum to 3. The other argument, provided by braham_snyder, employing the filling of buckets as defined by spaces between dividers, may be used to prove that the number of non-negative integer solutions of the sum of $$x_i$$s equal to $$k$$ is the same expression, you essentially have $$k$$ ones you need to distribute amongst $$n$$ bins, allowing some bins to contain none. The $$x_i$$s count the number of ones in the $$i^{th}$$ bin.

• Welcome to Math.SE. You've chosen an old (5+ years) Question (with Accepted and upvoted answers) to respond to, and while this is not necessarily a poor use of your time, there is no need to rush out a response. The Question asks for an explanation of "how this formula was developed". There might well be an opportunity to improve on what others have written, but you seem merely to assert that the formula is correct after restating it in terms of counting non-negative integer solutions. I don't know what HKA stands for. – hardmath Nov 19 '18 at 6:21