Pizza Problem

M

MLUCKHAM

New member
Joined
Aug 15, 2021
Messages
2
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!
 
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.
 
Dr.Peterson said:
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.
Click to expand...
Brilliant - thank you
 
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 [math]\frac{n!}{(n-k)!k!}[/math] it is called n choose k if you want to google it
 
The answer to your question is [imath]2^{20} = 1,048,576[/imath].

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.

[math]\dbinom{n}{k} = \dfrac{n!}{k! * (n - k)!}, \text { where}[/math]
[math]i! = 1 \text { if } i = 0, \text { and } i! = i * (i - 1)! \text { if } i > 0.[/math]
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

[math]\dbinom{n}{0} + \dbinom{n}{1} + \dbinom{n}{2} + \ ... \ \dbinom{n}{n - 1} + \dbinom{n}{n} = 2^n.[/math]
 
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.)
 
You must log in or register to reply here.
Top