(An archive question of the week)
We’ve been looking at examples of extended discussions with students about various kinds of problems. Here, we have one (not from a student) that led to some good thinking about combinatorics – the techniques of counting the ways something can happen.
The problem: Triple toppings
Here’s the question, from 2004 (not a paid product placement):
How Many Possible Pizza Topping Combinations? I work at Domino's Pizza and would like to tell customers how many topping combinations we have. It's tricky because you can get single-layers, double-layers, or triple-layers of ANY topping, and mix single, double, and triple-layered toppings on each pizza. There are 13 different toppings. You can get a pizza with 1 or up to 39 toppings (triple everything.) The fact that you can have a pizza with double pepperoni, triple sausage, and normal amount of green peppers makes it much harder. I took (39^13 + 26^13 + 13^13 and got 485,362,204,315,790,908,548)... that seems like a lot though, so I thought I had better ask an expert.
Questions about the number of ways to top a pizza (or make a sundae, or whatever) abound; this one is a little more challenging than many. For some other examples from our archive, see
Combinations of Toppings when Ordering a Pizza Gift Wrap Combinations Pascal's Triangle and the ice cream cones Shirts and Pants Fast Food Combinations
Ryan’s thinking shows some understanding of appropriate methods; using 13 as an exponent makes sense, since we have the same kind of choice to make about each of 13 items. His bases, however, are not appropriate. It appears he is trying to count separately the ways to have single, double, and triple toppings, but he has overcounted considerably.
Doctor Edwin took the question:
I love this question. You're right, it's a lot more interesting because of the possibility of single, double, or triple doses of each topping. There are a couple of ways to think about the problem. I'll start with the one that I think is the simplest, and then we can talk about the one I think is the coolest.
Problems in combinatorics typically can be solved in multiple ways; in fact, several of us have said that we never quite trust our work on such a problem until we get the same answer in more than one way. So offering two methods is common.
First method: One item at a time
He starts the way we often start with a big problem like this, “playing” with smaller numbers to get a feel for how it will work with bigger numbers, while also checking our understanding of the problem itself:
Suppose you had one topping, let's say mushrooms. How many different possible pizzas would there be? If I understand your setup right, there would be 4: no topping, single mushrooms, double mushrooms, or triple mushrooms. Now imagine that there are two toppings, mushrooms and sausage. How many possible combinations are there? Well, if a customer doesn't want mushrooms, there are 4, right? And if the customer wants 1x mushrooms, that's 4 more, and so on for 2x and 3x mushrooms. In other words, there are 4 x 4 = 16 different combinations with two items. We could continue this for a long time. If you have only sausage, mushroom, and onion, that's 16 combinations with no onion, 16 with 1x onion, and so on, for a total of 4 x 4 x 4 = 64 combinations. So it looks like the number of combinations is: (# of choices for item 1) X (# of choices for item 2) X ....etc. Now we have the same number of choices for each item, so that simplifies things a bit. Can you take it from there? Write back and tell me what you get.
Because the choice for each topping is independent, we multiply the number of ways to make each choice.
Let’s finish this up. For each of the 13 items on the menu, we have four choices (0, 1, 2, or 3 of them). So the answer is $$4\times 4\times 4\times 4\times 4\times 4\times 4\times 4\times 4\times 4\times 4\times 4\times 4 = 4^{13} = 67,108,864.$$ (Note that this includes a pizza with no toppings, which makes sense to me, but seems to have been excluded in the problem statement.)
Not as hard as it seemed, really. By approaching the decisions one topping at a time, we found a very straightforward method. One way to envision this process is to imagine an order sheet that lists all 13 toppings, with a box next to each to either leave blank, or fill in a number from 1 to 3. The key to the solution is the realization that 0 is also a number, so there are 4 choices for each.
Method 2: Encoding the order
The second method is really the same basic formula, but approached in terms of a different representation:
Now on to the cool part. Let's represent a pizza choice numerically. I can represent each topping with a number zero through three representing no topping through triple topping. If you're taking orders and calling them back to the cook, and there is only one topping (sausage) available and someone wants triple sausage, you could yell back, "Gimme a 3."
Now suppose again that there are sausage and mushroom available, and someone wants double sausage and single mushrooms. You could work out a system with the cook where you always list the ingredients in the same order. So then you could yell, "Gimme a 21."
So you could represent every possible pizza as a 13-digit number, where every digit was 0, 1, 2, or 3. I don't know how much you remember from math class (some, obviously, judging from your question), but you may have learned at some point to do math in different bases. Every pizza can be represented by a 13-digit number in base 4, and every possible number in base 4 represents a pizza. So the question then becomes, how high can you count in base 4 with only 13 digits?
0000000000000
0000000000001
0000000000002
0000000000003
0000000000010
0000000000011
0000000000012
0000000000013
0000000000020
0000000000021
... and so on
If that's unfamiliar or confusing, go back to thinking of them as toppings:
0x sausage, 0x mushrooms
0x sausage, 1x mushrooms
0x sausage, 2x mushrooms
0x sausage, 3x mushrooms
1x sausage, 0x mushrooms
1x sausage, 1x mushrooms
1x sausage, 2x mushrooms
1x sausage, 3x mushrooms
2x sausage, 0x mushrooms
2x sausage, 1x mushrooms
So, how high can you count in base 4 with 13 digits? Let me know what you come up with.
The idea of representing a problem in a different way is extremely useful in combinatorics. It’s especially useful if the new representation is more familiar to you than the original. In this case, if you’ve worked with bases, you know that just as in counting from 000 through 999 you have 1000 numbers (which is \(10^3\)), here we are counting from 0,0000,0000,0000 through 4,4444,4444,4444, and the next number is \(10,0000,0000,0000 = 4^{13}\). So that’s the answer this way. (I wrote the numbers with a comma every four places to help keep track of digits, because someone who found base 4 natural would probably do that … .)
That’s really the same sort of thinking as the first way, but using a different representation. Our 13 blank boxes have just become 13 digits.
Method 3: Sum over number of different toppings
Ryan gave it a try, but didn’t quite understand yet – that’s why we like conversations more than just answers. He wrote back:
Hey Doctor Edwin! Thanks for the help (and quick response!) I may have found the answer, but I'm not sure. I found the number of combinations for a 1-topping (39) and then the number of combinations for a 2-topping (741) and 3-topping (9139) and so on up to a 39-topping pizza (1 combination, [all the toppings]). I then added all the final numbers together and got "549,755,813,879". Is that correct? If so, I can happily tell people we have over half a trillion topping combinations, haha!
Ryan is thinking of a one-topping pizza as choosing one of the 13 toppings, then choosing 1, 2, or 3 of it, for a total of 39 pizzas; and so on. Since these are mutually exclusive, we can add up the 13 possible numbers to get the total. But it isn’t clear how he is counting multiple toppings, since he didn’t give details for his calculations.
Doctor Edwin replied:
Hi, Ryan. I think it's going to be a lot less than half a trillion. I think you and I are using a couple of words differently. When I said imagine you could only have one topping, I meant, imagine there was only one topping to choose from. You meant that you could only pick one topping, but you could pick any of the ones that are available in real life. The problem with your approach (and it can be solved that way, it's just more complicated) is that for my first choice I've got 40 possibilities (including plain). For my second choice I can't choose from 40 possibilities, because I've already used one of them. That is, suppose I choose sausage for my first topping. I can't choose 1x sausage or 2x sausage or 3x sausage for my second choice, can I?
Let’s try finishing Ryan’s method, and see how hard it will be.
For one topping, we saw above that there are \(13\times 3 = 39\) possibilities.
For two, we have to pick 2 of the 13 toppings, which we can do in “13 choose 2” ways: \({13\choose 2} = \frac{13!}{2!11!} = 78\). Then we have to pick a number of each of them, 1, 2, or 3. So the total is \({13\choose 2}\times 3 \times 3 = 702\). Ryan had said 741; that’s 39 too many. Possibly his numbers are partial sums instead of addends.
For three toppings, the same thinking leads to \({13\choose 3}\times 3^3 = 286\times 27 = 7722\). This is very different from Ryan’s 9139, so I don’t know just what he was doing.
Carrying this further, we get a sum of 13 terms: $$\sum_{i=1}^{13}{13\choose i}3^i.$$ If we just calculate these and add them up (I used Excel) we get the same answer as before – except that this excludes a plain pizza. My numbers are:
39 + 702 + 7,722 + 57,915 + 312,741 + 1,250,964 + 3,752,892 + 8,444,007 + 14,073,345 + 16,888,014 + 13,817,466 + 6,908,733 + 1,594,323 = 67,108,863
It appears from this that we should be able to prove a theorem that $$\sum_{i=0}^{n}{n\choose i}3^i = 4^n.$$ Without such a theorem, this method is not easy, though it was successful!
(There is, of course, a combinatorial proof of this summation: Each term of the sum represents the number of base-4 numbers with i non-zero digits, so the sum is, as we’ve seen, the number of all base-4 numbers. An algebraic proof is probably a little harder.)
Method 1, restated
So let’s move on; often a student needs a second perspective in order to understand an answer (which is part of the reason we are not bothered when two of us answer a question, each with a slightly different method, or a different way to say the same thing):
So instead of thinking of it that way (how many could I get if I pick only one, how many if I pick only one or two, etc.), let's think of it the other way (how many could I get if there is only one topping to choose from, how many if there are only two toppings to choose from?).
In that case, for each of my 13 toppings, I've got 4 possibilities: zero, 1x, 2x, or 3x.
With only one topping to choose from, I've got 4 pizzas I could order. With two toppings to choose from, I've got 4 choices for my first topping. For each of those, I've got 4 choices for my second topping, for a total of 4 x 4 = 16 choices. Let's try that out and count them. We'll use M for mushrooms and S for sausage:
0M 0S
0M 1S
0M 2S
0M 3S
1M 0S
1M 1S
1M 2S
1M 3S
2M 0S
2M 1S
2M 2S
2M 3S
3M 0S
3M 1S
3M 2S
3M 3S
That's every combination we can make if we only have two ingredients to play with. Let's say we add onions to the menu. If someone wants no onions, they've got 16 choices. If they want 1x onions, that's another 16 possible pizzas they could order. 16 more for 2x onions, and 16 more for 3x onions. In other words, with three toppings on the menu, there are 4 x 16 = 4 x 4 x 4 = 64 possible toppings to choose from.
So a general formula would be
(number of ways to use a single topping) ^ (number of toppings)
where the number of ways to use a single topping includes not using any. So for your example, the total number of possible pizzas to choose from is
4 ^ 13
Not anywhere near a half-trillion, but it's a heck of a big number, isn't it? I'm surprised I ever manage to order a pizza at all.
Here, rather than calculating each number and adding, we are generalizing from the small examples to obtain our simple final answer.