In this exercise, we will explore problems in which we have to choose r items from n different varieties. Consider this example: a taco restaurant offers three options of taco to choose from. You can pick a steak taco, a chicken taco, or a veggie taco. You wish to order a total of eight tacos. In this situation, the set of tacos is S = {chicken, steak, veggie} which has three distinct elements and you wish to order more than three.

How many ways can you do this? If the sequence matters, the answer is 3⁸. How many ways are there to do this if the sequence doesn’t matter? The brute force way to compute this calculation is to consider every possible combination of tacos and then sum them all up. While this calculation would work it is not efficient! We need a better way.

Let’s say you present your order in the following manner: xx|xxxx|xx. This means you want two chicken tacos, four steak, and two veggie. This order xxx|xxx|xx means you want three chicken, three steak, and two veggie. This illustrates the technique we can use to determine how many different ways there are to order eight tacos. This means that we have ten available spaces for tacos (x) and two delimiters (|). So to answer the question, out of the ten available spots we choose eight of them for tacos and the remaining spots for delimiters.

$C(10, 8) = \binom{10}{8} \binom{2}{2} = 45$

45 different combinations of tacos!

To put it formally, when selecting r items from a multiset of n distinct items we have:

$C(r + n - 1, r) = \frac{(r + n - 1)!}{r!(n-1)!}$

Different combinations. Note that we have n-1 because the amount of delimiters we need is one less than we have items in our multiset.