Math help re: combinations

[JonInMiddleGA]

Okay, I'm smart enough to know when I know just enough to be dangerous, both to myself and those around me. Since this is work related, I'd rather like to get it right so I'm hoping some of the math gurus around the FOFC will help me out.

I've Googled and read more possible methods & examples than I can shake a stick at, I've gone through several passes at this & get a different (quite plausible) answer each time. About the only thing that I think I'm sure about is that the problem/solution involves combinations instead of permutations.

I'll start with the basic question and then add on the bits that make it more complex than the usual example.

Q1) If you have N different ingredients for a pizza, how many different pizza combinations can you make? The groundrules are that, for now, nothing is doubled - it's either on the pizza or not on the pizza.

Is this as simple as 2 to the N power?

(Q1b) If "no toppings at all" is an option, how do I account for that? Simply +1 to the answer above? Or is that possibility already included in the answer to Q1?

(Q2) If we've answered the first two questions, then we add this part: how do I handle double cheese (the only ingredient which can be doubled in this exercise)? I can't just double the answer to Q1 because any pizza that didn't have cheese cannot have double cheese. I'm pretty sure I can't just treat it as an extra ingredient (i.e. N becomes N+1) because it's dependent upon the on/off choice for single cheese. I'm flummoxed on this part for sure.

(Q3) Once I get a solution to the questions above, I have one more task to complete to arrive at the desired final number: how do I handle the various options for Crust + Sauce combos? I think I know the answer to this one: it's the solution for Q2 times the number of different sauce/crust combinations. Makes sense to me, if there was only a single possible combination then the answer is whatever we get for Q2 ... but if there's 2 crusts & 1 sauce (for example) then everything topping combination possible is now possible twice..

Any & all help is appreciated, the goal here is not only get an answer but to understand how it's derived well enough to be able to explain it to several other "non-math" people (their own description). I'm the "math-iest" guy in the bunch unfortunately.

In case someone would prefer to use the actual number instead of just N for the number of possible ingredients ... N = 44 (including cheeses)

[Abe Sargent]

<iframe width="420" height="315" src="http://www.youtube.com/embed/w0i_ZFlGTVY" frameborder="0" allowfullscreen></iframe>

[Izulde]

Including cheeses? So is there more than one cheese that can be doubled?

[stevew]

http://mathforum.org/library/drmath/view/66561.html

Did you come across this in google?

[Passacaglia]

1. Yeah, I'd say 2 to the N power. Each item is a coin flip, basically. No toppings is equivalent to all heads, all topping is all tails.

2. Half of the combinations have cheese. So if 1 is 2 to the N, take half that number, and add it to your orginal answer.

3. Yes.

[JonInMiddleGA]

Including cheeses? So is there more than one cheese that can be doubled?

Dammit, you immediately asked the question that I started pondering more deeply after I posted.

Here's the deal in actual numbers:
35 ingredients and 9 cheeses

I added the two things together when I posted thinking "okay, a customer could order anything from a zero cheese to a nine cheese pizza"

Only after I walked away from posting did I realize "oh shit, what if they double more than one of those cheeses?" ... which I don't technically know for sure is even an option.

So basically you now know as much as I know.

[Passacaglia]

For #2, you could also look at it like for each topping, you've got two options (on or off), but for cheese, you have three options (on, off, double). So your answer is 2 to the N-1, times 3.

Or, 2 to the 35th times 3 to the 9th. Assuming cheeses are not part of the 35.

[JonInMiddleGA]

http://mathforum.org/library/drmath/view/66561.html

Did you come across this in google?

Twice :)

I seemed to get bogged down (or maybe they got bogged down) in the issue of double or even tripling all ingredients. I wasn't entirely confident that I wasn't getting lost in all that somewhere. Buuuuuut this bit (number of ways to use a single topping) ^ (number of toppings) seems to be a match for my current working guess for basic Q1 being "2 to the N" (since in the most basic form I have only 2 ways: on or off)

[JonInMiddleGA]

For #2, you could also look at it like for each topping, you've got two options (on or off), but for cheese, you have three options (on, off, double). So your answer is 2 to the N-1, times 3.

Or, 2 to the 35th times 3 to the 9th. Assuming cheeses are not part of the 35.

Cheeses are not in the 35. That's just veggies & meat (plus tofu).

[britrock88]

Started responding myself, but then read Pass's answers, which are dead on.

[JonInMiddleGA]

Okay, so with 2^35 times 3^9 ... I get 6.7630273e+14

But guess what ... that only represents 1 crust type + 1 sauce type.
I've got three crusts & 9 sauces

So for each crust it's 6.7630273e+14 TIMES 9 (to cover the sauces)
And then that number TIMES 3 (to cover the crusts)

Right?

I mean, is this actually possible to comprehend? Hell, is this actually possible?
Over 18 quadrillion combinations possible? Srsly?

[britrock88]

That's the answer. And yeah, the number is stratospheric.

There was a burger chain (Burger King? Wendy's?) that touted the 729 ways to make their burger years ago. That was a simpler matter -- 3 possible amounts of a condiment (none/normal/extra) for 7 condiments (lettuce/tomato/onion/pickle/ketchup/mustard/mayo). So when you compare how many more options you have in terms of crusts and pizza toppings, the magnitude of the number begins to make more sense.

[Julio Riddols]

Today I learned there are more pizza combinations available in this problem than there are unique fingerprints in the world.

[Buccaneer]

I also learned they eat a lot of pizza in the South.

[JonInMiddleGA]

I also learned they eat a lot of pizza in the South.

Eh, I wouldn't worry too much. A lot of the combinations are too healthy to be anything anybody would actually eat ;)

Others are even stranger ... such as the pepperoni bacon tofu combo with olive oiil on gluten free crust included in that still-hard-to-image number.

[Passacaglia]

Okay, so with 2^35 times 3^9 ... I get 6.7630273e+14

But guess what ... that only represents 1 crust type + 1 sauce type.
I've got three crusts & 9 sauces

So for each crust it's 6.7630273e+14 TIMES 9 (to cover the sauces)
And then that number TIMES 3 (to cover the crusts)

Right?

I mean, is this actually possible to comprehend? Hell, is this actually possible?
Over 18 quadrillion combinations possible? Srsly?

Can you have extra sauce? Can you have more than one sauce, or no sauce? Or is it just "choose one of these 9" (as your model indicates)? I'd imagine it's that way with crust, but I get extra sauce all the time.

[JonInMiddleGA]

Can you have extra sauce? Can you have more than one sauce, or no sauce? Or is it just "choose one of these 9" (as your model indicates)? I'd imagine it's that way with crust, but I get extra sauce all the time.

My instructions did not include any mention of extra sauce.

There's 18 quajillion combinations as it is, do we really need to go down the extra sauce route? ;)

[Passacaglia]

My instructions did not include any mention of extra sauce.

There's 18 quajillion combinations as it is, do we really need to go down the extra sauce route? ;)

I dunno -- it's your thing, not mine. I didn't even know you had instructions. :p

[JonInMiddleGA]

I dunno -- it's your thing, not mine. I didn't even know you had instructions. :p

I was told -- roughly -- what I was supposed to consider. They're a little shaken by the answer though, they were thinking something in the millions.

[Passacaglia]

Yeah, if it's work-related, i.e. something that would be in an ad, the number is too silly to have any meaning, I'd think.

[Passacaglia]

Maybe they could compare their number to a corresponding number for other pizza places?

[JonInMiddleGA]

Yeah, if it's work-related, i.e. something that would be in an ad, the number is too silly to have any meaning, I'd think.

We shall see where they go with it. I did my part, provided the number. I'll let the left-brainers play with it for a while.

It really does feel to me like a number too big for people to get their heads around (or believe is actually real rather than just some b.s. number).

If/when they settle on something (and the client - hopefully - approves) I'll definitely share back here. Probably be February'ish if my guess is right.

[Passacaglia]

Wait, there's left-brainers involved, and they're not the people calculating the number?

[JonInMiddleGA]

Wait, there's left-brainers involved, and they're not the people calculating the number?

Shit. I said it backwards. They're complete right-brains, I'm what passes for a left-brain in this configuration.

[ozias]

The only combination that matters is what I want on the pizza when I order it. :D