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
- crust (4 types, choose 1)
- size (4 types, choose 1) some crusts are limited to a certain size – not accounting for that, but would like to.
- cheese (5 types, choose 1)
- sauce (4 types, choose 1)
- sauce level (3 types, choose 1)
- meats (9 types, choose up to 9)
- 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:
- crust $binom{4}{1}=4$
- size $binom{4}{1}=4$
- cheese $binom{5}{1}=5$
- sauce $binom{4}{1}=4$
- sauce level $binom{3}{1}=3$
- meats $2^9 = 512$
- 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 + {15choose 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 $4times 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
