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/