Fast Food Combinations

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.

Suppose the McKing chain of restaurants has a menu with three items (a hamburger, french fries, and a drink). For the sake of brevity, we'll denote these items as H, F, and D.

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 two hamburgers and a drink, or a hamburger and three orders of fries, or anything like that, because obviously there is no limit to the number of ways you can do this, which makes it somewhat pointless to calculate.

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?

Combinations

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!

Permutations

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
CABD
ACB -> DABC
ACDB
ACBD
ABC -> DABC
ABDC
ABCD
BA -> CBA -> DCBA
CDBA
CBDA
BCA -> DBCA
BDCA
BCDA
BAC -> DBAC
BDAC
BACD
-    ---   -----  ----
1     2      6      24       (Number of items)

= 1    1*2   1*2*3  1*2*3*4
```
Do 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.

With 8 items on your menu, the number of possible combinations will be 28 = 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 lot bigger than 40312, since the last term alone is 40320. (Adding it up, using a spreadsheet, we find that it's 109601.)

So wherever McDonald's got this number, we know that it is not

• 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 256 - 9 = 247.