(An archive question of the week)
While gathering combinatorics questions, there were several that stood out. This one will serve well to summarize the topic, showing multiple methods for counting, and contrasting other kinds of problems.
The problem
The question, from 2007, relates to an Arby’s promotion:
How Many Different Dinners Can Be Ordered? 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?
Dave is representing the common notation \(\displaystyle _nC_r = \frac{n!}{r!(n-r)!}\) (read as “n choose r” ) for combinations. He has done very well. Doctor Wilko chose to expand on what he did:
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.
The first step, always, is to clarify the problem, restating it if necessary to expose all assumptions that are required:
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.
So this is not a straight permutation or combination problem, both of which involve subsets of a given set, with no repetition allowed. In this case, the items are distinguishable but repeatable; order doesn’t matter.
A good model for the choice of a meal would be a menu list, with a blank for each item in which you put how many of that item ordered; these numbers have to add up to 5:
____ Arby’s Melt
____ Small Drink
____ Ham Melt
____ Small Fries
____ Potato Cakes
____ Turnover
____ Chicken Sandwich
____ Shake
First method: multiple cases
The first is just a little different from Dave’s method, and has a slightly different order:
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.
This case (like the others) could also be counted in other ways. For example, we could just use a permutation to choose two items in order, the first to be the 4 and the second to be the 1. This gives \(\displaystyle _8P_2 = \frac{8!}{6!} = 8\cdot7 = 56\) as before.
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.
Doctor Wilko’s result can be written as $$_8C_1\ +\ _8C_2\ \cdot\ _2C_1\ +\ _8C_2\ \cdot\ _2C_1\ +\ _8C_3\ \cdot\ _3C_1\ +\ _8C_3\ \cdot\ _3C_1\ +\ _8C_4\ \cdot\ _4C_1\ +\ _8C_5.$$
Dave’s version was $$_8C_1\ +\ _8C_2\ \cdot\ 2\ +\ _8C_2\ \cdot\ 2\ +\ _8C_3\ \cdot\ _3C_1\ +\ _8C_3\ \cdot\ _3C_1\ +\ _8C_4\ \cdot\ _4C_1\ +\ _8C_5,$$ which is identical.
My version, using permutations, is $$_8C_1\ +\ _8P_2\ +\ _8P_2\ +\ _8P_3 \div 2!\ +\ _8P_3 \div 2!\ +\ _8P_4 \div 3!\ +\ _8C_5.$$
These are all essentially the same idea.
Finding the cases
How do we know we haven’t missed a case? Dave made an orderly list, though it isn’t entirely clear what principle he was using to do so. Here is a list of the 7 cases used, in Doctor Wilko’s order, expressed by representing each kind of item with a letter:
- AAAAA
- AAAAB
- AAABB
- AAABC
- AABBC
- AABCD
- ABCDE
We can see that he used the ordering principle of largest-first, where items are listed in decreasing order of frequency in each case, and the number of the first item mentioned decreases from case to case. In this order, it is easy to see that nothing was missed. This is the main benefit of Doctor Wilko’s work over Dave’s, and it is essential when you use cases.
Keep in mind that here the letters don’t stand for specific items; the main work was to count the number of distinct ways in which a meaning could be assigned to each letter.
Note that we could also list these cases as sums that total 5:
- \(5\)
- \(4+1\)
- \(3+2\)
- \(3+1+1\)
- \(2+2+1\)
- \(2+1+1+1\)
- \(1+1+1+1+1\)
These are the “unordered partitions” of 5 (since we are not distinguishing different orders of the same number), which are harder to count (without listing as we have done here) than other things we’ve discussed. Fortunately, what we needed to do was to list them, not just to count! If you are curious, see here:
Number of Unordered Partitions
Second method: Stars and bars
This will look familiar from last time. I am rewriting his to use stars and bars in the classic form, whereas he swapped the symbols, using the bars as tallies. Here we will directly use my menu list order form from above as a model.
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 stars under the 8 items in any manner you choose.
We could also think of each choice as a partition — this time as an ordered partition in which there must be 8 terms, any of which can be zero. We might have started a list like this:
- \(5+0+0+0+0+0+0+0\)
- \(4+1+0+0+0+0+0+0\)
- \(4+0+1+0+0+0+0+0\)
- …
- \(4+0+0+0+0+0+0+1\)
- \(3+2+0+0+0+0+0+0\)
- …
This would not be easy to list, would it? Nor is it obvious in this form how you could count them. But this time, there is a nice formula (as we saw last time)! In the world of partitions, you can be surprised by what is easy and what is hard.
We just make the mental twist to see the first example above merely as * * | | * | | * | | | *:
The "leap" with this method is to now see this as a permutations problem where you are arranging 5 stars and 7 bars, where 5 stars are identical and the 7 bars 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!
He closes this with a comment that many of us have made:
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!
In algebra, I always want to check my work by plugging the solution into the original problem; in combinatorics I never fully trust my work until I can get the same answer two ways.
Incorrect methods
Doctor Wilko then provided a catalog of basic formulas for different kinds of problems, showing why they don’t apply. The most important step in a combinatorics problem is determining what kind of problem it is, and what model or method applies. A mistake there ruins everything you do.
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. ==================
The model for this is _ _ _ _ _, where each of the 5 blanks (the items ordered) can be filled in any of 8 ways (the items on the menu), independently, so the total is \(8\cdot 8\cdot 8\cdot 8\cdot 8\). The trouble is that the blanks are distinguishable, so that order counts.
For our problem, this would overcount, as we would be counting each meal multiple times. This is how you might count the ways for 5 distinct people to each choose one item, or to arrange 5 items in a 5-part tray. But we don’t want to distinguish the order of a meal.
Note that we can’t correct for this by dividing by the number of arrangements of each meal, as we do in creating the formula for combinations, because that varies according to the number of duplicates. AAAAA has only one arrangement, while ABCDE has 60 arrangements.
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. ==================
The model for this is _ _ _ _ _, where each blank must be filled with a different item, so the total is \(8\cdot 7\cdot 6\cdot 5\cdot 4\).
This is wrong both because order counts (as it shouldn’t for our problem) and because repetition is not allowed (as it should be). Nothing is as we need it to be.
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 nCr = n!/[r!*(n-r)!] (Combinations without Repetition) where n is the number of total objects and r is the number chosen. ==================
One way to derive this formula is to start with the \(8\cdot 7\cdot 6\cdot 5\cdot 4\) permutations, and divide by the \(5\cdot 4\cdot 3\cdot 2\cdot 1\) ways to arrange each combination.
We do need combinations for our problem, because the order in which we choose items doesn’t matter; but we need to allow for repetitions.
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. ==================
This is the formula we found last time, using \(n-1\) bars (separating n bins) and r stars. The name nPr is probably a typo; there is a symbol for this (which I never learned), namely \(\displaystyle \left({8 \choose 5}\right)\).