How Many Different Dinners Can Be Ordered?
Date: 05/25/2007 at 14:58:32 From: Dave Subject: Arby's 5 for $5.95 I was trying to calculate the number of different meals you can get for the 5 for $5.95 at Arby's and wasn't confident in the way I was calculating it. Given 8 different choices, how many combinations of 5 are there? You do not need to choose different entrées. I am confused about the fact that you are calculating a combination with replacement. I thought that I would start this way... 8 C 1 for the possibility of choosing 5 entrées alike, 2*(8 C 2) for choosing 4 alike and 1 different entrée. Multiplied by 2 because there are 2 ways to assign each pair of choices. 2*(8 C 2) for choosing 3 alike and 2 alike and multiply by 2 because there are 2 ways to assign each pair. (8 C 3)*(3 C 1) for choosing 2 alike, 2 alike and 1 different entrée and once the three are chosen, choose the one that is single. (8 C 3)*(3 C 1) for choosing 3 alike, 1 different, 1 different. (8 C 4)*(4 C 1) for choosing 2 alike, and 3 different entrées plus choosing which one is doubled up. (8 C 5) to choose all 5 entrées different. Then add each of the above together. Am I on the right track?
Date: 05/25/2007 at 23:54:31 From: Doctor Wilko Subject: Re: Arby's 5 for $5.95 Hi Dave, Thanks for writing to Ask Dr. Math! Yes, your approach to the problem looks excellent. I like this problem a lot. I think it's a good real-world problem. We often see many restaurants and pizza parlors trying to figure out how many different combinations of meals or pizzas they offer. The difficulty with these problems is that it is easy to calculate the number of combinations incorrectly. I'll present two solutions below to answer, "How many combinations of 5 items for $5.95 can one order from Arby's 8-item menu?" The first uses the same logic you applied in your work, and the second approaches it slightly differently. Then I'll also show some errors that are commonly made on this sort of problem. Recall, we are assuming: - There are 8 choices on this particular menu. - 5 items can be ordered (for $5.95). - Duplicate items can be ordered (the 5 items don't have to be distinct). The last point is important. There are not 8 finite items to choose from; there are 8 choices on the menu and you can order anywhere from 0-5 of each of those items. =========================== Method 1 =========================== For this solution, I'll try to explicitly enumerate the different ways I can order items from the menu and then apply the combinations formulas respectively. Last I'll add up all the answers to get the final answer. I'm basically partitioning the sample space into smaller subproblems, solving each subproblem, and then combining the results to answer the big problem. 1. I can order 5 of the same item. There is only 1 choice. Which of the 8 should I choose? Mathematically, this can be written as, 8C1 = 8. There are 8 ways I can choose 1 item--once I pick it, then I can order a quantity of 5 of that 1 item. 2. I can order 4 of one item and 1 other item. Here, there are only 2 choices. Out of the 8 menu items, which 2 should I choose? Mathematically, this can be written as, 8C2 = 28 But out of those two choices, I need to order 4 of one and 1 of the other. To figure out which of the items I order 4 of, I can multiply by 2C1 or 2. The final answer for this portion of the problem is, 8C2 * 2C1 = 28 * 2 = 56. Note, at this point, you could explicitly enumerate all the ways to order 4 of one item and 1 other item from the menu of 8 items. You'll see that there are 56 combinations. If I continue with the same reasoning as above, the problem continues as follows: 3. 3 same items, 2 other same items 8C2 * 2C1 = 56. 4. 3 same items, 1 other item, 1 other item 8C3 * 3C1 = 168. 5. 2 same items, 2 other same items, 1 other item 8C3 *3C1 = 168. 6. 2 same items, 1 other item, 1 other item, 1 other item 8C4 * 4C1 = 280. 7. 5 different items 8C5 = 56. Total combinations of 5 items I can order from a menu of 8 items at Arby's is, 8 + 56 + 56 + 168 + 168 + 280 + 56 = 792. Apparently, Arby's boasts "Over 790 combinations!". Arby's claim gives me confidence in this answer. Let's look at the problem in a different way and see if we can confirm this answer. =========================================== Method 2 =========================================== This solution is a little more elegant, but perhaps not as initially intuitive as trying explicit enumeration. I credit another one of our volunteers, Dr. Anthony, for reminding me of this technique. Let's label the menu items as A-H. You are ordering from the menu of 8 items. You may tally up your order like this: Item A * B * C * D * E * F * G * H --------------------------------------------------- || * * | * * | * * * | Meaning 2 of item A, 1 of item C, 1 of item E, and 1 of item H. There are other possibilities, too. For instance, Item A * B * C * D * E * F * G * H --------------------------------------------------- ||| * * || * * * * * Meaning 3 of item A and 2 of item C. You could do this for many different combinations, but should soon realize that every possible order can be made by placing 5 tally marks under the 8 items in any manner you choose. The "leap" with this method is to now see this as a permutations problem where you are arranging 5 bars and 7 stars, where 5 bars are identical and the 7 stars are identical. From probability, the permutations formula for this is, 12! ------- = 792. 5! 7! You can also think of it as you have 12 spaces and you can choose a place for the 5 *'s in 12C5 ways. Likewise, you have 12 spaces and you can choose a place for the 7 |'s in 12C7 ways. Note, 12C5 = 12C7 = 792. This confirms our answer from above! My favorite technique with combinations/permutations problems is to find more than one way to solve the problem. If I get confirmation from two different approaches, I usually feel more confident in my answer! ============================ Incorrect Solutions ============================ Below are a couple of incorrect solutions and reasons why they are incorrect. 1. 8^5 = 32,768 It seems logical at first, you have 8 choices for your first choice, 8 choices for your second choice, etc... I was actually guilty of thinking this was the answer at first! But then it hit me that this is a PERMUTATIONS solution. For instance, you would have ABBCC and BBACC. These are just two different permutations of the same combination of 5 items. In our problem, we want to buy a sack of 5 items from the 8-item menu. Order is irrelevant in purchasing the 5 items. ================== In general, when order matters, and objects can be chosen more than once, the number of permutations is n^r (Permutations with Repetition) where n is the number of total objects and r is the number chosen. ================== 2. 8P5 = 6,720 This assumes 8 finite, distinct items, and you want all the different arrangements of 5 of them. ABCDE would be a different permutation than EDCBA. Remember, for the problem, we want the number of possible combinations a person could physically order from the menu. Order doesn't have anything to do with this. ================== In general, when order matters, and each object can only be chosen once, the number of permutations is nPr = n!/(n-r)! (Permutations without Repetition) where n is the number of total objects and r is the number chosen. ================== 3. 8C5 = 56 This assumes 8 finite, distinct items, and you are choosing 5 of them. This is not representative of the problem. This solution wouldn't let you order 5 roast beefs, for example. ================== In general, when order doesn't matter, and each object can only be chosen once, the number of combinations is nPr = n!/[r!*(n-r)!] (Combinations without Repetition) where n is the number of total objects and r is the number chosen. ================== So, finally, that leads us back to our solution, which really is a "combinations with repetition" problem. ================== In general, when order doesn't matter, and each object can be chosen more than once, the number of combinations is nPr = (n+r-1)!/[r!*(n-1)!] (Combinations with Repetition) where n is the number of total objects and r is the number chosen. ================== - Doctor Wilko, The Math Forum http://mathforum.org/dr.math/
Date: 05/30/2007 at 08:44:20 From: Dave Subject: Thank you (Arby's 5 for $5.95) Thank you for your solutions and comments. I'm glad to hear that I was on the right track. I can't believe that I didn't think of the partitioning method, how elegant!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.