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 38. 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.
45 different combinations of tacos!
To put it formally, when selecting r items from a multiset of n distinct items we have:
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.
Instructions
You have two buckets and a collection of red balls, green balls, and black balls. How many ways are there to fill the first bucket with 12 balls and the second bucket with eight balls?
First, compute the number of ways to fill up the first bucket with 12 balls. Store your answer in the first_bucket
variable.
Compute the number of ways to fill up the second bucket with eight balls. Store the answer in the second_bucket
variable.
How many ways are there to fill up the first bucket with 12 balls and the second bucket with eight balls? Store your answer in the num_ways
variable.