Dr. Math FAQ || Classic Problems || Formulas || Search Dr. Math || Dr. Math Home

For a basic review of concepts, see Permutations and Combinations. ## Fast Food Combinations: How many possible combinations can be made from a special menu of eight items?Several contributors noticed when McDonald's introduced a special menu with 8 different items. An ad claimed that this creates 40312 possible combinations. Is this true? One of the things that makes the subject of combinations and
permutations so frustrating is that the numbers involved grow so
quickly that they can become intimidating even for relatively small
problems. So let's look at a smaller problem, to make sure that we're
using our terms clearly. The possible 'combinations' (that is, the various ways that you can select up to three items) from the menu would be {} Nothing {H} Hamburger {F} Fries {D} Drink {H,F} Hamburger and fries {H,D} Hamburger and drink {F,D} Fries and drink {H,F,D} Hamburger, fries, and drink Note that we're not taking duplicates into account. For example,
we're not going to worry about buying Also, note that we're not taking order into account. For example, from the point of view of computing combinations, {H,D} (a hamburger and a drink) is really the same thing as {D,H} (a drink and a hamburger). This isn't to say that we can't take order into account; for example, we might want to treat a hamburger on the left side of a tray differently from one on the right side of a tray: +-----+ +-----+ | H D | | D H | +-----+ +-----+ But when we start considering order, we've moved from 'combinations' (selections) into 'permutations' (arrangements). Once we take permutations into account, we get more possibilities: Combinations Permutations ------------ ---------------------------- {} {} {H} H {F} F {D} D {H,F} HF, FH {H,D} HD, DH {F,D} FD, DF {H,F,D} HFD, HDF, FHD, FDH, DHF, DFH So if order counts, and if you can buy zero or one item of each kind, then the total number of possibilities for a menu of three items is 16. (Note that this includes the possibility of buying nothing at all; for example, maybe you just dropped in to get a free game piece for McKing's current Lord of the Monopoly Stone game promotion.) Up to now we've looked at an example with three items on the menu. How can we compute this number of 'possibilities' for a larger menu? Can we find a formula for the general case of N items?
Let's consider combinations first. One easy way to think about combinations is to build up a pattern from small cases. The simplest possible case is no items: {} Now if we add an item, we still have all the combinations we had before (i.e., we can ignore the new item), or we can add the new item to each of those cases: {} -> {} {a} If we add another item, we can do the same thing -- keep the old cases, or add the new item to each of the old cases: {} -> {} -> {} {b} {a} -> {a} {ab} And again: {} -> {} -> {} -> {} {c} {b} -> {b} {bc} {a} -> {a} -> {a} {ac} {ab} -> {ab} {abc} A little thought shows that each time we add a new element, the number of combinations doubles. items combinations ----- ------------ 0 2^0 = 1 1 2^1 = 2 2 2^2 = 4 3 2^3 = 8 . . 10 2^10 = 1024 . . 20 2^20 = 1,048,576 Note that the numbers grow pretty quickly!
Now, since we're considering order, each of these combinations has a number of permutations. Again, it can be instructive to work our way up from small cases. If we have no elements, there is only one way to arrange them: {} -> {} Also, if we have one element, there is one way to arrange it: {A} -> A If we add a new element, we can place it at either end of the previous arrangement: A -> AB BA If we add another element, we can place it at every possible location in the previous arrangements: A -> AB -> CAB C in front ACB C in middle ABC C at end BA -> CBA C in front BCA C in middle BAC C at end And again: A -> AB -> CAB -> DCAB CDAB CADB CABD ACB -> DABC ADCB ACDB ACBD ABC -> DABC ADBC ABDC ABCD BA -> CBA -> DCBA CDBA CBDA CBAD BCA -> DBCA BDCA BCDA BCAD BAC -> DBAC BDAC BADC BACD - --- ----- ---- 1 2 6 24 (Number of items) = 1 1*2 1*2*3 1*2*3*4Do you see what's happening? Each time we add a new element, we multiply the previous number of permutations by the new total number of elements. We have a shorthand for this kind of growth, called the 'factorial' operator: 1! = 1 factorial = 1 2! = 2 factorial = 2 * 1 3! = 3 factorial = 3 * 2 * 1 In general, N! = N * (N-1)! e.g., 4! = 4 * (3!) and by definition, 0! = 1 (This last definition is a little strange, but useful.) So we can extend the table that we started for combinations: items combinations permutations ------ ----------- ------------ 0 2^0 = 1 0! = 1 1 2^1 = 2 1! = 1 2 2^2 = 4 2! = 2 3 2^3 = 8 3! = 6 4 2^4 = 16 4! = 24 5 2^5 = 32 5! = 120 . . N 2^N N! Now -- finally! -- we're in a position to answer your original question.
^{8} = 256.And if you bought all 8 items, and tried to arrange them in different orders on your tray, the number of arrangements ('permutations') would be 8! = 40320. As you've no doubt noticed, neither of these numbers is 40312, which raises the question of how McDonald's might have come up with that number. Perhaps they're computing permutations OF combinations? Going back to our HFD example, Combinations Permutations ------------ ---------------------------- {} {} {H} H {F} F {D} D {H,F} HF, FH {H,D} HD, DH {F,D} FD, DF {H,F,D} HFD, HDF, FHD, FDH, DHF, DFH we can see that the total number of possibilities (figuring out the number of arrangements for each combination) is complicated to compute for the general case. We have to enumerate the selections; compute the number of arrangements of each selection; and add those up: total = 1*(0!) + 3*(1!) + 3*(2!) + 1*(3!) 3 For 4 items, this would be total = 1*(0!) + 4*(1!) + 6*(2!) + 4*(3!) + 1*(4!) 4 For 8 items, it would be +-----------------+ | | v | | total = 1 * (0!) | 8 + 8 * (1!) | + 28 * (2!) +--- Number of ways to select N items. + 56 * (3!) + 70 * (4!) + 56 * (5!) +--- Number of ways to arrange them. + 28 * (6!) | + 8 * (7!) | + 1 * (8!) | | ^ | | | +------------+ To see where I'm getting the numbers (1, 8, 28, 56, 70, 56, 28, 8, 1), take a look at the Dr. Math FAQ on Pascal's triangle. This total is going to be a So wherever McDonald's got this number, we know that it is - the number of ways that you can select up to 8 items
(which is 256); or
- the number of different ways that you can arrange 8 items on a tray
(which is 40320); or
- the number of ways that you can select up to 8 items AND arrange them on a tray (which is 109601).
Perhaps McDonald's wanted to exclude the 8 'combinations' that contain exactly one item. They might then have calculated 40320 - 8 = 40312. However, you can't subtract 8 combinations of exactly one item from permutations of eight items. No matter how you arrange eight items (permutations), there are no combinations with only 1 item; they all have eight. You can't subtract apples from oranges. Not only that, the 'combination' that contains no items at all should probably also be excluded, and that would reduce the total by 9, not 8. The number of combinations with at least two items is Back to Permutations and Combinations. |

[**Privacy Policy**]
[**Terms of Use**]

Math Forum Home ||
Math Library ||
Quick Reference ||
Math Forum Search

© 1994- The Math Forum at NCTM. All rights reserved.

http://mathforum.org/