Any maths buffs?

1x2x3x4x...up to the no of toppings.

[code]
ABC=/=ACB etc.
AABC=/=ABC
There are N different toppings available.
A pizza can have any whole number of toppings from 0 to X.
AAB counts as 3 toppings.

Number of different pizzas available =

Number of possible pizzas with 0 toppings 1 (=N^0)
+number of possible pizzas with 1 topping +N^1
+number of possible pizzas with 2 toppings +N^2
+... +...
+number of possible pizzas with X toppings. +N^X

I think.
[/code]

ftfy?

my ability to produce words from maths is poor (its been 4 years since I had to use it properly)

All combinations of the three toppings as singles = the same pizza.
ie ABC= CBA= BAC=etc.

and yes AABC=/= ABC.

i think n^x might work, but I'm not convinced its the right one.

[code]
ABC=ACB etc.
AABC=/=ABC
There are N different toppings available.
A pizza can have any whole number of toppings from* 1* to X.
AAB counts as 3 toppings.

(N^1)/1+(N^2)/2+...+(N^X)/X

Possibly this then.[/code] EDIT this is not right.

Saying that topping order matters seems a little unrealistic. While putting the cheese on before the tomato would make a very different pizza, who'd notice the relative order of small toppings like bacon and mushrooms? But let's start with it.

If you have n different items, they can be arranged into n x (n-1) x (n-2) x ... 2 x 1 = n! = factorial(n) ways, because there are n choices for the first item, then having chosen one there's one less to choose from for second item, and so on.

But rather than arranging all n possible toppings in order, we only have to pick m of them, so we only need the first m terms of the multiplication above. We can write this with factorials as n!/(n-m)! as dividing by (n-m)! cancels out the following n-m terms of n!.

If we aren't interested in all the different permutations of topping order but only in the number of possible topping combinations (or we only allow one order per combination) then we have over-counted by a factor of the number of ways we can order the m items we pick, so we need to divide by m! to get n!/(n-m)!m! possible pizzas.

Alternatively if we do care about order and also will allow the same topping to be picked any number of times (and each number counted as a different pizza), then there are n^m possible pizzas with m toppings chosen from a menu of n.

If were allowed to pick up to k toppings, then you need to add up all the results for m=0, m=1, m=2 ... m=k.

you need to sum up the number of different combination for each number of toppings.

the number of topping combination's without repeats for 1 topping out of n
+
the number of topping combination's without repeats for 2 toppings out of n
+
.
.
.
.
+
the number of topping combination's without repeats for m toppings out of n

this will be the answer.

\sum{1}{k=m}\frac{n!}{(n-k)!n^{k}}

in tex speak. where n is number of ingredients and m is number of ingredients allowed to make up each topping.

ah bugger beaten to it

But re-reading, i don't think i've answered your actual question.

but in other news, this is good for you recreational mathematicians out there

http://pyrgic.blogspot.com/

But re-reading, i don't think i've answered your actual question.

actually same here. the factorial formula is for no repeats in the AAA sense when we need the ABC = BCA case. I'm to tired to work this out at the mo so maybe I'll do it tomorrow when I'm supposed to be doing PhD maths.

oooh maybe cyclic permutations of ABC are the same but CBA is different???????

linear algebra applied to pizza, galios would be happy!

In which case, a Hawaiian wouldn't commute with anything.

I think i've got it now?

If you are allowed up to k toppings, then you can pick a combination of m (m <= k) toppings from the n available, then distribute up to k-m 'extras' among the m toppings (e.g convert bacon & mushroom to bacon and tripple mushroom (4 toppings)).

My textbook tells me* there are (e+m-1)!/e!(m-1)! ways of sharing out e extras among the m toppings chosen.

So with n possible toppings and k max toppings per pizza:

sum from m = 1 to k { sum from e = 0 to k-m { n!(e+m-1)! / (n-m)!m!e!(m-1)!}}

• 1 for the null pizza

• The permutations formula n! only works if all n items are distinguishable. If m of them are identical then you need to divide by the m! ways they can be arranged. Putting e balls into m boxes is equivalent to picking a permutation of e identical balls and m-1 identical box-dividers.

D.q.e?

1 topping = 1 pizza.
2 toppings = 3 choices
3 toppings = 6 choices
and so on.

^ wrong.
1 topping= at least 2 pizzas:
A and AA
2 topping= 8 pizzas.
AB, A, B, AAB, ABB, AA, BB, AABB

anyway, its confusing the hell out of me, so I'm glad to see the level of maths needed is way beyond my level.

I edited the original q to make more sense (I hope)

Incidentally, Double toppings are allowed, but Triple toppings are not, acc. Domino's options.
so AA can exist but AAA cannot.

What this means to the above equation I don't know.

what about AABB?

and is there a max toppings per pizza limit?
and do doubles count twice against that limit?

why would you want pineapple twice on your pizza ?

what if one of the toppings was another pizza, itself with another pizza as a topping, itself with ano...

what then? eh?

Anyway, ignoring the double toppings, the answer is this:

n = total number of toppings available
r = number of toppings on current pizza combination
t = total number of pizza choices

t = Σ(r = 0 to n) nCr

Double toppings add some complexity, as cheese_1 = cheese_2 when used alone (i.e. pizza {pepper,cheese_1} = pizza {pepper,cheese_2}, but neither are equivalent to pizza {pepper,cheese_1,cheese_2})

So for each pizza with r toppings, there are 2^r possible pizzas with double toppings

eg. pizza = {ham,pineapple}
can also be
p_2 = {ham,double pineapple}
p_3 = {double ham, pineapple}
p_4 = {double ham,double pineapple}

So for n toppings, there are:
t = (
(nC0) * 2^0

• (nC2) * 2^2
  
• (nC3) * 2^3
  ...
  
• (nCn) * 2^n
  )
  
  

pizzas.

I think.

So if you have 10 toppings, and can double them up on any pizza, there are 59,049 distinct pizzas to choose from by my reckoning.

If you can't double up on toppings, only 1,024 pizzas.

what about AABB?

and is there a max toppings per pizza limit?
and do doubles count twice against that limit?

Forgot AABB, it counts.
Don't think there is a max toppings per pizza.

why would you want pineapple twice on your pizza ?

because is ace!

Anyway, ignoring the double toppings, the answer is this:

n = total number of toppings available
r = number of toppings on current pizza combination
t = total number of pizza choices

t = Σ(r = 0 to n) nCr

Double toppings add some complexity, as cheese_1 = cheese_2 when used alone (i.e. pizza {pepper,cheese_1} = pizza {pepper,cheese_2}, but neither are equivalent to pizza {pepper,cheese_1,cheese_2})

So for each pizza with r toppings, there are 2^r possible pizzas with double toppings

eg. pizza = {ham,pineapple}
can also be
p_2 = {ham,double pineapple}
p_3 = {double ham, pineapple}
p_4 = {double ham,double pineapple}

So for n toppings, there are:
t = (
(nC0) * 2^0

• (nC2) * 2^2
  
• (nC3) * 2^3
  ...
  
• (nCn) * 2^n
  )
  
  

pizzas.

I think.

I don't think this works when fed back the data....

Share your data...

i may have misread it... and missed the second part.
will be back when I have a working calculator.

(incidentally i meant when n=1, t=2 and when n=2 t=8)

I think it does work, it's relatively intuitive:

nCr gives you the number of distinct pizzas you can make with r toppings each, with n toppings to choose from.

Then, if you have the opportunity to double each topping on your pizza, each distinct pizza above has a further 2^r combinations

Then sum for all values of r (0 to n)

Have you considered this, in your calculations: