Combinations with Repetition II

Here's a hard question:

You're in the store and they have 6 kinds of fruit for sale (Apples, Bananas, Cherries, Dates etc.). You need to buy 4 fruit in total, but you can take any number of each fruit. For example, you could buy 3 apples and 1 date. How many ways you could choose 4 fruit?

In the case of combinations without repetition you were able to convert the standard Permutation formula (of R elements) to a standard Combination formula by dividing by r!. However this case is more difficult, so you need some other way to avoid counting Different Permutations Of the Same Combination (DPOSC).

Before scrolling down for the solution, see if you can figure out an approach on your own. How can this problem be converted to a problem like the last one or to the String of Beads case?

Getting Rid of DPOTSC
Instead of allowing the fruit to appear in any order, make sure they are all arranged in one order, say alphabetically. This way there will only be 1 permutation possible for each combination, so you've avoided the problem of DPOTSC. Also, now all you need to do is specify where to change from one fruit to the next, without worrying what that fruit is.

Representing the Combinations
In the last problem, you could just see how many ways there were to put a "divider" to separate between different types, and you can do similarly here. In this case, you'll need 5 dividers to 'separate' between 6 different types of fruit (even though you'll only be choosing 4 actual fruit).

You could represent every fruit as a star and every divider as a bar |. Whenever you go from one fruit type to the next, you can just put another bar, and multiple bars to move "ahead" multiple fruit. For example, if you chose 3 apples, and one date, you could represent it as:

1. ★ Take Apple
2. ★ Take Apple
3. ★Take Apple
4. | Divider for Bananas
5. | Divider for Cherries
6. | Divider for Dates
7. ★ Take Date
8. | Divider for Elderberries
9. | Divider for Figs

★ ★ ★ | | | ★ | |

Any combination of fruit can just be converted to an arrangement of stars and bars. How many ways can you arrange these 4 stars and 5 bars? This is the same problem as ordering the beads! So you just need to choose 5 of 9 slots to be bars and the problem is solved:

9 choose 5 = 126

Note that you can equivalently choose 4 of 9 spots to be fruit/stars since:
(9 choose 5) = (9 choose 4).

General Formula for Combinations with Duplicates
When choosing r from n elements, there are n-1 bars and r stars, for a total of n+r-1 positions. You then need to choose r of those elements (to be stars). So the formula can be written as:

Spelling out the formula This works fine, but if you were stranded on an island without a smartphone, you would need to solve that formula with a stick in the sand, so we'll plug it into the combination formula. You just insert (n-1+r) in place of 'n' in the regular formula.