Pizza Problem

[MLUCKHAM]

I just spent the weekend with my friend who owns a Pizza business. He currently offers 20 toppings for his pizzas and we wondered if there was a formula we could plug in the number of toppings and get the right answer out. All of the permutations or combination calculators I have tried so far seem to be off. These are the specific rules: -

The pizza can have anything from 1 to n toppings. No topping or combination of toppings can be duplicated - e.g. you can’t have 5 lots of pepperoni! The order is not important so Topping A, B, C is the same as C, B, A so is not allowed.

We looked at 5 toppings and we think the answer for 5 is 28. If we label each topping A, B ,C ,D ,E the combinations we allow for our rules are: -

A

B

C

D

E

Ab

Ac

Ad

Ae

Bc

Bd

Be

Cd

Ce

De

ABC

Abd

Abe

Acd

Ace

Ade

Bcd

Bce

Cde

Abcd

Abce

Bcde

Abcde

I cannot find an online calculator where I put in 5 and get 28 back. What am I missing? Any help you can offer may allow me to find out the answer to my friends conundrum - the answer to 20 toppings!

 

[Dr.Peterson]

You missed a few.

There should be C(5,1) = 5 ways to choose 1, C(5,2) = 10 ways to choose 2, C(5,3) = 10 ways to choose 3 (you listed 9), C(5,4) = 5 ways to choose 4 (you listed 4), and C(5,5) = 1 way to choose 4, for a total of 31, not 28.

But the easy way is to think of check boxes. Put a box next to each topping, and you can either check it or not. That gives 2^5 = 32 ways to check them; make it 31 if you don't allow a plain pizza with no toppings.

And that generalizes so that with 20 toppings, there are 2^20 = 1,048,576 combinations or so.

 

[MLUCKHAM]

You missed a few.

There should be C(5,1) = 5 ways to choose 1, C(5,2) = 10 ways to choose 2, C(5,3) = 10 ways to choose 3 (you listed 9), C(5,4) = 5 ways to choose 4 (you listed 4), and C(5,5) = 1 way to choose 4, for a total of 31, not 28.

But the easy way is to think of check boxes. Put a box next to each topping, and you can either check it or not. That gives 2^5 = 32 ways to check them; make it 31 if you don't allow a plain pizza with no toppings.

And that generalizes so that with 20 toppings, there are 2^20 = 1,048,576 combinations or so.

Brilliant - thank you

 

[Otis]

my friend … currently offers 20 toppings for his pizzas

What's the price for a large, 20-topping pizza?

?

 

[AbdelRahmanShady]

you can use this formula to calculate how many permutations of topping can you get with n topping if you choose to put k of them
you $$\frac{n!}{(n-k)!k!}$$ it is called n choose k if you want to google it

 

[JeffM]

The answer to your question is $2^{20} = 1,048,576$.

Proving this may be a bit beyond high school algebra.

How many ways can you choose no topping out of a choice of 20 toppings. 1 obviously.

How many ways can you choose one topping out of a choice of 20 toppings. 20 obviously. So that makes a total so far of 21.

The formula given in the previous answer will tell you many distinct ways you can choose k toppings out of n distinct choices when no topping may be duplicated.

$$\dbinom{n}{k} = \dfrac{n!}{k! * (n - k)!}, \text { where}$$
$$i! = 1 \text { if } i = 0, \text { and } i! = i * (i - 1)! \text { if } i > 0.$$
But you want to know how many ways you can choose any number of toppings out of n possible

As Dr. Peterson said, that is equal to

$$\dbinom{n}{0} + \dbinom{n}{1} + \dbinom{n}{2} + \ ... \ \dbinom{n}{n - 1} + \dbinom{n}{n} = 2^n.$$

 

[Harry_the_cat]

Is pineapple one of the toppings?

 

[HallsofIvy]

A little simpler way of seeing this is to realize that, for each of the 20 toppings, you have to decide to include it or not. That is a "yes-no" decision 20 times so there are $\displaystyle 2^{20}$ ways those 20 decisions could go so $\displaystyle 2^{20}$ possible combinations. (Every decision could be "no" so that includes no topping at all.)