# How many combinations am I truly offering?

I am currently running a promotion for my company and we would like to truly explain how many combinations exist for the product. Here is how the steps break down:

• Step 1: Customer orders Rice or Salad version
• Step 2: Customer orders a protein: Chicken, Taco Beef, Steak or Veggie
• Step 3: Customer orders beans: black beans, pinto beans, refried beans (customer may order no beans, 1 bean, 2 beans, all bean options)
• Step 4: Add any or all of these toppings: Shredded Cheese, Pico, Romaine Lettuce Mix, Grilled Onions/Peppers, Fiesta Corn Salsa, Chipotle Citrus Vinaigrette, or Creamy Jalapeno Ranch.
• Step 5: Add any or all of these toppings: Crumbled bacon, Guacamole, Sour Cream, Queso.
-
Can you solve simpler related problems? For example, if you offered option 1 or option 2, and then option A or option B, how many options would there be? – Ben Millwood Sep 17 '12 at 20:39
This question has made me hungry :( – Emily Sep 17 '12 at 20:41
Some of these combinations might be isomorphic. Is the cheese in step 4 different from the queso in step 5? – Trevor Wilson Sep 17 '12 at 21:00
Does "any or all" choices out of $n$ mean that the number of toppings chosen must be either $1$ or $n$, as a strict interpretation would suggest? And if the more lenient interpretation of "any subset" is applied, why separate steps $4$ and $5$? – Marc van Leeuwen Sep 18 '12 at 9:54

Hint: For each of the first two steps, the customer chooses one of a list, so you multiply the number of options at each step. For the last three steps, you can make each item into a separate step and the choice is yes or no. How many options is that?

-

Below, the $\binom{n}{k}$ notation refers to choose, which tells you the number of ways you can choose $k$ items from a collection of $n$.

Step 1: 2 choices.

Step 2: 4 choices.

Step 3: It's the number of ways to choose $0$ items from $3$, plus the number of ways to choose $1$ item from $3$, etc.... $\binom{3}{0} + \binom{3}{1} +\binom{3}{2} +\binom{3}{3} = 8$ choices

Step 4: Similar to step 3, there are 7 items, you can choose between 0 and 7 of them, so there are $\sum_{k=0}^{7} \binom{7}{k} = 2^7 = 128$ choices.

Step 5: There are 4 items and you can choose between 0 and 4 of them, so there are $\sum_{k=0}^{4} \binom{4}{k} = 2^4 = 16$ choices

For the total number of combos you multiply these numbers together, so there are $2\cdot 4 \cdot 8 \cdot 128 \cdot 16 = 2^{17} = 131072$ total combos.

-
It might be good to point out that this works out the same as the simpler method in the other answer because $\sum_{k=0}^n \binom{n}{k} = 2^n$. – Trevor Wilson Sep 17 '12 at 20:55
@TrevorWilson, status update: I just went and told a fellow student about this wonderful fact you've revealed to me. He really liked it. We're going to go talk about it some more. Thanks again! – user41583 Sep 17 '12 at 21:06
@TrevorWilson, we chatted about it for a while and I think we just proved that $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$!!! :-) BTW, re your comment above: queso is a condiment found frequently at mexican restaurants. It's a kind of liquid cheese whiz mixed with salsa kind of thing and it is distinct from regular cheese so the two are quite different I think. – user41583 Sep 17 '12 at 23:02
[I have deleted my earlier comments, which were totally off the mark. It seems that I confused the "factorial" symbol with some punctuation indicating enthusiasm for the binomial theorem. How embarrassing!] – Trevor Wilson Sep 19 '12 at 17:44
@TrevorWilson, I'm an enthusiastic chap. That clears everything up! – user41583 Sep 19 '12 at 17:50