Formula for Combinations With Replacement

Question

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?

Answer 1

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 $k$ black circles in the row and $(n-k)$ white ones in the row, so the permutations of this row is precisley:

$$\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 cleverly assigning 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.

Answer 2

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.

Answer 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]

Answer 4

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.