Combinations with repetition
The number of combinations with repetition can be calculated as:
For example, if you have ten types of donuts (n) on a menu to choose from and you want three donuts (k) the number of ways to choose can be calculated as:
There is an easy way to understand the above result. Imagine we have n + k identical boxes arranged on a line. From these boxes (except the first one), we arbitrarily choose k of them and mark the chosen boxes as empty. The rest of the boxes can be filled by the n elements in the set S. For each non-empty box, if it is followed by M successive empty boxes, we choose the corresponding element in the non-empty box M times. As a result, each arrangement of choosing empty boxes corresponds to a way of choosing k out of the n elements with repetition. The total number is therefore the number of combinations with repetition, which equals
Example 2
Another explanation, which might help. Imagine you have slots (or boxes) for 4 types of fruits (apple, orange, pear, banana), all next to one another at the grocery store. That means n=4. If you choose a type of fruit, you want to mark that box so you put a '1' into that slot. You want to choose 12 fruits, and you can choose one type of fruit more than once. Therefore, altogether you'll put 12 '1's into the fruit slots. That means k=12. Now imagine that each separator of a slot is marked by a '0'. For the 4 boxes you will have 4-1=3 separators.
If you want to choose 2 apples from the first slot, 3 oranges from the second, 5 pears from the third, and 2 bananas from the fourth, that would be denoted by 11 0 111 0 11111 0 11 . The number of ways we can choose 12 fruits from the 4 boxes (or slots) is simply the number of ways we can put 12 '1's and 3 '0's into order. Thus the total number of ways is the permutation of 12 '1's and 3 '0's. Expressed with k and n:
k = 12; n = 4;