Pizza 73 (math)

Factual Questions
1

First of all, this is not homework, but merely a curious inquiry. In my province, there is a chain of pizza stores called Pizza 73. This restaurant offers something called a 4-Pak, in which you can choose four types of food from:

  • Two-topping pizzas with a choice of 17 toppings, two different crusts, and two different sauces.
  • Two different types of chicken wings
  • A giant cookie

You can also pick the same thing more than once (e.g., you can pick four cookies).

The chain claims that there are ~3.7 billion different combinations, but they also are open to the possibility that they made an error in their calculations. I am aware that the amount of combinations should be that high, but I’d just like to know what kind of numbers the brilliant minds of the Straight Dope come up with. So, just how many different ways can one choose a 4-Pak?

Btw, I think we can assume that one cannot have zero toppings or two of the same toppings, but one can have only one topping if they desire.

2

It’s been a while since I’ve had statistics, but I’ll give it a shot…

OK…I see a total of 26 different combos (counting all pizza combos as just one for the moment):
4 pizzas
3 pizzas, 1 wing (2 combos)
3 pizzas, 1 cookie
2 pizzas, 2 wings (3 combos)
2 pizzas, 1 wing, 1 cookie (2 combos)
2 pizzas, 2 cookies
1 pizza, 3 wings (4 combos)
1 pizza, 2 wings, 1 cookie (3 combos)
1 pizza, 1 wing, 2 cookies (2 combos)
1 pizza, 3 cookies
4 cookies
4 wings (5 combos)

Note that in the above, I’m assuming that order doesn’t matter - “pizza, pizza, cookie, cookie” is the same as “pizza, cookie, cookie, pizza”, etc.

Now, for each pizza, I see 1,156 total combinations:
17 toppings (first choice) *
16 remaining toppings, plus the possibility of zero toppings (second choice) *
2 crust types *
2 sauce types = 1156

Now, here’s where things (i.e., my calculations) get a little iffy.
For the 4-pizza combo, I would think you’d have 1156[sup]4[/sup] possible combinations, or about 1.78 trillion.
For the 3-pizza combos, you’d then have 1156[sup]3[/sup] * 3 (since there are 3-3 pizza combos) = 4,634,413,248
For the 2-pizza combos (6 total): 1156[sup]2[/sup] * 6 = 8,018,016
For the 1-pizza combos (10 total): 1156 * 10 = 11560
And 6 no-pizza combos. Add them all up, and you get…oh…about 1.79 trillion.

So, either I’m way off, or they’re way off :smiley:

3

You also left out
3 wings 1 cookie (4 combos)
2 wings 2 cookies (3 combos)
3 cookies 1 wing (2 combos)

Which, out of 1.79 trillion combinations, aren’t significant at all. :slight_smile:

I’ll try to check everything later, when I’m less tired, but that all looks ok…

4

That makes a “Onion-Pepperoni” pizza different from a “Pepperoni-Onion” pizza. Order shouldn’t be important.

I get: 18 toppings (17+no topping)
*18 toppings (17+no topping)
-18 (To subtract off all the “double” toppings)
/2 (to account for order being unimportant)
*2 crust types
*2 sauce types

Grand Total, 612 different kinds of 2 topping pizzas.

5

Leapin’ Lizards, might as well finish what I think the answer is…

612 pizzas + 2 kinds of wings + 1 giant cookie= 615 different items to order.

You can choose: 4 of the same
3 of the same/1 different item
2 of the same/2 of another
2 of the same/1 of another/1 of yet another
4 different items

4 similar items: 615 ways to order this

3 of the same /1 different: 615*614 = 377,610

2 of the same/2 of another: 615*614/2 = 188,805

2 of the same/1 of another/1 of yet another: 615614613/2 = 115,737,465

4 different items: (615614613612)/(4321) = 5,902,610,715

Grand Total = 6,018,914,595 ways

6

Normally, pizza places will let you have no toppings on deals like that, since it saves them money. But since that’s a rule in the OP, I’ll discount it…

Here’s what I get for possible pizzas:

The formula for x items chosen out of a possible n is:


   n!
--------
(n-x)!x!

So…we’re taking any 2 items out of a possible 17, which gives 17!/(17-2)!2! = 355,687,428,096,000/(1,307,674,368,000 x 2) = only 136 different possibilities. Of course there are the 17 other options (1 item) also, giving a total of 153. Each of these can be had with one of 2 crusts (306) and 2 sauces, that’s 612 different pizzas, as 23skidoo said.

612 pizzas, 2 wings, 1 cookie

So if you have 4 pizzas, with 612 possibilities on each, that gives 612[sup]4[/sup] = 140,283,207,936
3 pizzas, one of anything else: 612[sup]3[/sup] each with 3 choices = 687,662,784
3 of any non-pizza item with 1 pizza: 3*612 = 1,836
3 of any non-pizza with 1 other non-pizza item = 6
2 pizzas with 2 identical non-pizza items = 612[sup]2[/sup] x 3 = 1,123,632
2 pizzas with 2 different non-pizza items = 612[sup]2[/sup] x 3 = 1,123,632
2 non-pizzas with 2 other non-pizzas = 3
1 pizza with 1 of each of the other items = 612

SO…
140,283,207,936 + 687,662,784 + 1,836 + 6 + 1,123,632 + 3 + 612 = a grand total of 140,973,120,441.

I really feel like I’m missing something, so if anybody can find the error in my reasoning, I’d like to know what it is.

7

This would be what I forgot from my statistics days :slight_smile:
But hey, being off by about 30 billion isn’t too bad, right?

8

Or even about 1.6 trillion (mummble mummble…stupid zeroes…mummble mummble)…

9

616 kinds of pizzas:

17 choose 2 = 136 ways to combine 2 toppings
17 ways for 1 topping
1 way for no toppings

Joe Cool counted right, except that he missed the no topping pizza.

These are all exclusive, so we have a total of 154 ways to do toppings or lack thereof.

154 times 2 times 2 for the crust and sauce choice gives us 616 pizzas.

The various 4paks:

4p
3p1w
3p1c
2p2w
2p1w1c
2p2c
1p3w
1p2w1c
1p1w2c
1p3c
4w
3w1c
2w2c
1w3c
4c

Now, you might be tempted to just multiply by factors of 616 and 2 depending on how may p’s ands w’s there are, but that would be wrong because of ordering considerations again - it doesn’t matter whether the anchovie and mushroom job is the first pizza or the third one. The correct way to approach the 4p case, for instance is:

616 choose 4 (all the ways of choosing 4 different pizzas) +
616 choose 3 * 3 (choosing three different and picking one to have 2 of) +
616 choose 2 * 3 (choosing two different pizzas, which can either be split 2-2 or 3-1 either of two ways) +
616 ways to have 4 identical pizzas

616 choose 4 = 5,941,189,870
616 choose 3 = 38,767,960
616 choose 2 = 189,420

if I did my arithmetic right, giving me around 6 billion for the 4p case, which is definitely going to be the dominant term. If I simply consider the 136 2 topping pizzas * 4 = 544:

544 choose 4 = 3,608,976,376

This will dominate. I suspect this is where the pizza chain arrived at their number - they weren’t counting 1 and no topping pizzas as possibilities.

10

BTW, when I say “n choose m”, I mean the formula Darwin’s Finch gave - which is the number of unique ways of picking combinations of m unique items out of n, and a convenient thing to remember. What the formula boils down to when you calculate it is “multiply n, n-1, n-2 together until you get down to the larger of m or n-m. Then divide by the smaller of m or n-m factorial”, so 616 choose 4 for instance is simply (616615614613)/(4321).

11

Why can’t the 2 toppings be the same like double-cheese?

That would make 137 2-topping pizzas, and 3,716,599,705 combinations. I think.

12

The easiest way to solve this problem is to break it up.

The total amount of two-topping pizzas that can be formed with
18 toppings (‘nothing’ is a topping), 2 crusts, and 2 sauces is:

(18 * 17) / 2 * 2 * 2
or 18 * 17 * 2 = 612

(Note it was divided by two- that’s because we want combinations, not permutations- this is a key difference between
my answer and previous answers)

There are three different ways you can order the chicken wings (two of one type, one of each, and two of the other type)

Now we go on to the giant cookie- there’s only 1 way you can have that.

Ok, so now we have to put it all together:

Someone just getting pizza:
612^4 (4p) 140283207936

Someone just getting wings:
3^4 81

Someone just getting cookies:
1 1

Someone ordering pizza and chicken wings:
612^3 * 3 (3p1w) 687662784
612^2 * 3^2 (2p2w) 3370896
612 * 3^3 (1p3w) 16524

Someone ordering pizza and cookies:
612^3 (3p1w) 229220928
612^2 (2p2w) 374544
612 (1p3w) 612

Someone ordering cookies and chicken wings:
3^3 (3w1c) 27
3^2 (2w2c) 9
3 (1w3c) 3

And to sum it all up (bear with me):
140283207936 + 81 + 1 + 687662784 + 3370896 + 16524 + 229220928 + 374544 + 612 + 27 + 9 + 3

141,203,854,345

13

You’re coming out way high because that is ORDERING them - you are picking one of 612 for the first pizza, 612 for the second pizza, etc. You wind up counting 4 pizzas of types a, b, c, d as different than c, b, a, d for instance. That’s what I was getting at above. You can get a decent approximation by dividing by 24 for all the possible orders, but there are some permutations with duplicates, like a, a, b, c versus a, c, a, b. Using your 612 (nobody likes no topping pizzas anyway):

612 choose 4 = 5,787,999,945
and you add

612 choose 3 * 3 +
612 choose 2 * 3 +
612

to arrive at the 4 pizza combinations.

As I said, if you don’t take 1 topping pizzas into account:

544 choose 4 = 3,608,976,376

just a hundred million shy of the pizza parlor’s figure, and without running the numbers I can easily believe that all the other cases will add up to about 100,000,000, certainly not more than 200,000,000. The ways of choosing 4 pizzas is far larger than any of the other things.

Anybody want to order a pizza?

14

Just to clarify, it wasn’t me…it was Joe_Cool who gave the formula. I botched it up when I did it :smiley:

15

They probably define two-topping pizza like this: “A two-topping pizza has exactly two different toppings.”

Using that definition, we get this:

17 (choices for the first topping)
*16 (choices for the second topping)
/2 (to account for order being unimportant)
*2 (different sauces)
*2 (different crusts)=

544 different kinds of pizza.

544 kinds of pizza + 2 kinds of wings + 1 kind of cookie = 547 different items to order

You can choose:
4 identical items
3 identical items/1 other item
2 identical items/2 other “matching” items
2 identical items/1 other item/1 “different” other item
4 un-identical items

4 identical items: 547 ways

3 identical items/1 other item: 547*546 = 298,662

2 identical items/2 other “matching” items: 547*546/2 = 149,331

2 identical items/1 other item/1 “different” other item: 547546545/2 = 81,385,395

4 un-identical items: (547546545544)/(4321)= 3,689,471,240

Grand Total: 3,771,305,175 different ways. Roughly, 3.7 billion.