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?

Solution 1:

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.

Solution 2:

A useful way to think about it:

Imagine you have $n$ different cells form left to right. A combination without replacement of $k$ objects from $n$ objects would be equivalent to the number of ways in which these $k$ objects can be distributed among the cells with at most one object per cell. The key here is that due to the fact that there is no replacement there is only one or zero objects in each cell. It is easy to see that this corresponds to a combination without replacement because if we represent the occupied cells with a black circle and the empty cells with a white one there would be a row of $k$ black circles and $(n-k)$ white ones, then the permutations of this row is percisley:

$$\frac{n!}{(n-k)!k!}=\binom{n}{k}$$

$$[][x][x][][x](...)[x][]= \bigcirc \bullet \bullet \bigcirc \bullet (...)\bullet \bigcirc $$

Note here that necessarily $k\leq n$.

Using the same analogy for combinations with replacement we have $k$ objects that we want to distribute into this $n$ cells but now we can put more than one object per cell (hence with replacement) also note that there is no bound on $k$ because if $k>n$ then we can just put more than one object in each cell. Now here comes the tricky part, we can count the permutations of this set by celverly assining circles. Let the division between the cells be a white circles and the objects black circles, then there would be $(n-1)$ white circles and $k$ black ones. It's not so hard to see that each permutation of these circles corresponds to a different way of putting each these $k$ objects into the $n$ cells. We have a total of $(n-1)+k$ circles, $(n-1)$ white and $k$ black, so the number of permutations of this row of circles is percisley:

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

$$[][xxxx][xx][][x][(...)][x][]=$$

$$\bigcirc \bullet \bullet \bullet \bullet \bigcirc \bullet \bullet \bigcirc \bigcirc \bullet \bigcirc(...)\bigcirc \bullet \bigcirc $$

This is not really a rigorous way of proof but I think it illustrates the concept well. If you want a slightly more detailed explanation and exercises I recommend the book Introduction to Combinatorics published by the United Kingdom Mathematics Trust (UKMT) available at their webpage. It covers many interesting topics with a problem solving approach to them.

Solution 3:

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]