Associated Topics || Dr. Math Home || Search Dr. Math

### How Many Possible Pizza Topping Combinations?

```Date: 12/21/2004 at 05:47:47
From: Ryan
Subject: Dominos Pizza - How Many 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.

```

```
Date: 12/21/2004 at 08:57:11
From: Doctor Edwin
Subject: Re: Dominos Pizza - How Many Topping Combinations?

Hi, Ryan.

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.

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.

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.

Thanks for writing.  You owe me a 121 (1x sausage, 2x mushroom, 1x
onion).

- Doctor Edwin, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 12/22/2004 at 05:56:19
From: Ryan
Subject: Dominos Pizza - How Many Topping Combinations?

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

```

```
Date: 12/22/2004 at 09:00:22
From: Doctor Edwin
Subject: Re: Dominos Pizza - How Many Topping Combinations?

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?

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.

- Doctor Edwin, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/