Pizza commercial claim of 34 million combinations

Problem Detail: 

A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out. Here's what I have so far: From the online ordering site I got the choices

1. crust (4 types, choose 1)
2. size (4 types, choose 1) some crusts are limited to a certain size - not accounting for that, but would like to.
3. cheese (5 types, choose 1)
4. sauce (4 types, choose 1)
5. sauce level (3 types, choose 1)
6. meats (9 types, choose up to 9)
7. non-meats (15 types, choose up to 15)

So I figured this was a combination problem (order is not important) and not an n choose k problem, null is allowed for anything but crust and crust, size, cheese, sauce and sauce level would all be choose only one. Meats and non-meats $2^?$? So that would be:

1. crust $\binom{4}{1}=4$
2. size $\binom{4}{1}=4$
3. cheese $\binom{5}{1}=5$
4. sauce $\binom{4}{1}=4$
5. sauce level $\binom{3}{1}=3$
6. meats $2^9 = 512$
7. non-meats $2^{15} = 32768$

At this point I'm stuck, how do I combine these to arrive at the total number of possible combinations?

I found this site helpful.

ETA: If I don't account for the limitations on crust size - some crusts are only available in certain sizes - there are over 16 billion; 16,106,127,360 combinations available, so they were off by quite a bit.

Asked By : gebuh

Answered By : Ran G.

Ok, A bit more detailed answer than in the comments.

Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$.

The interesting part are things like the non-meat options. You have 15 and can choose any set of up to 15. Mathematically, this means ${15 \choose 0} + {15 \choose 1} + \cdots + {15\choose 15}$.

As you mentioned, there is a nice formula for such sums: $$\sum_{i=0}^n {n \choose i} = 2^i$$ thus, for the non-meat options you have $2^{15}=32768$ options, as you said. (see here for more formulas).

Lastly, to combine all the options, you just multiply them. If you have 4 possible sizes, and, say, 4 possible crusts, then you have $4\times 4=16$ different combinations overall.

So, multiplying everything you get 16.106.127.360, which is larger than 34 million.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3141