Cfrgtkky

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.

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.

$defmultichoose#1#2{{left(kern-.3emleft(genfrac{}{}{0pt}{}{#1}{#2}right)kern-.3emright)}}$I really like one of the explanations within Wikipedia's article on multisets — in summary of that intuition: $multichoose{3}{5}$ is equivalent to counting the number of ways you can fill 3 distinct buckets with 5 (initially non-distinct) elements in total. This is one such filling:

$$color{blue}{star star star} mid star mid color{red}{star} $$

And a second such filling (buckets can be empty):

$$color{blue}{star star} mid star star star mid$$

The number of ways we can fill $n$ distinct buckets with $k$ elements total corresponds to the number of ways we can place $n-1$ (non-distinct) bars among $k$ stars, as illustrated above. That latter part can be rephrased as: the number of ways we can place $n-1$ bars into $(n-1) + k$ total characters, which brings us to:

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

The name of that graphical aid is "stars and bars" — that article also contains an explanation similar to the one above.

The concept of "combinations with replacement" is also sometimes referred to as "multichoose". Wikipedia notes that this is additionally equivalent to counting multisets:

The number of multisets of cardinality k, with elements taken from a finite set of cardinality n, is called the multiset coefficient or multiset number.

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.