1. Sep 29, 2010

### bizzlekizzle

I work for a company that touts that there are over 250,000 possible ways to dress their hamburger. We offer 15 condiments. As far as I can remember from high school math, that is a "function" of 15 (15!). To find all possible combinations of condiments would require an equation of 15x14x13x12x11... all the way to 1. This results in over 3 trillion possible combinations. Am I wrong or is my company seriously underselling it's potential?

2. Sep 29, 2010

### G037H3

do any condiments have to be paired with other condiments?

3. Sep 29, 2010

### Staff: Mentor

Can you put all 15 condiments on the hamburger at the same time, or is there a limit?

Don't expect upper management to be able to understand this discussion.

4. Sep 29, 2010

### CRGreathouse

It would be 15! only if you counted the order of the condiments, requiring that all were used. If order doesn't matter and a person can choose 0 to 15 condiments, it's 2^15 = 32,768. To get over 250,000 you'd need 18 condiments.

5. Sep 29, 2010

### bizzlekizzle

GO37H3, They don't have to be paired, you can get as many or as few as you like.

Last edited: Sep 29, 2010
6. Sep 29, 2010

### bizzlekizzle

CRGreathouse, Is that 2 to the 15th power (2x2x2... 15 times)? BTW, this is going to sound odd, but did you manage a Burger King about 15 years ago?

Last edited: Sep 29, 2010
7. Sep 29, 2010

### CRGreathouse

2 to the 15th power, yes. That's 15 "2"s with 14 multiplication signs between them.

8. Sep 29, 2010

### pallidin

I wonder if the company is also factoring in condiment density.
That is, one pickle or 7, for example.

9. Sep 30, 2010

### bizzlekizzle

No, one cannot specify how many pickles. However, there are specs for "light" and "extra", but only for rigidly quantifiable (sp?) items i.e. Extra pickles, but not extra mustard. There are four such items, so the extra 8 options (light and extra) still far exceeds 250000 (8.3 million+). Anyway, I'm sure they did not put this much thought or logic into it.

Last edited: Sep 30, 2010
10. Sep 30, 2010

### rhenretta

Possibly because I am a programmer, I like to think of these problems in turns of binary. Represent each condiment by an index in a string of 15 binary digits:

011100010100101 = C

Each one of those can represent if the specific condiment is present (1) or not (0). If $$C_{0}$$ represents ketchup, then since the value is 1 it is present. Thus the number of options is equal to the highest possible value of C, which is 111111111111111 or in decimal terms: 32,767. Either whataburger is lying, or perhaps you miscounted the condiments?

Last edited: Sep 30, 2010
11. Sep 30, 2010

### bizzlekizzle

It's not Whataburger, and I can count.

12. Sep 30, 2010

### DrGreg

If I understand this correctly:

For 11 items there are two options: yes or no

For 4 items there are four options, none, light, regular or extra.

That makes a total of 211 × 44 = 524,288.

So incorrect only by a factor of two.

13. Oct 1, 2010

### bizzlekizzle

I consider myself a smart guy, not highly educated, but very smart. I don't understand why I don't get this. The 4 to the 4th makes sense, four items have four possible states of being, so to speak. It's the 2 to the whatever power I don't get. Why 2?

14. Oct 1, 2010

### bizzlekizzle

I suppose it's because the other 11 have two states of being, there or not there.

15. Oct 1, 2010

### Staff: Mentor

Exactly.

16. Oct 5, 2010

### zgozvrm

Take a simpler example. Suppose there are only 3 condiments (a, b, & c) that can be added (and no "light" or "heavy" option), how many ways to make the burger are there then?

The answer is 8 (assuming order doesn't matter):
You can opt for no condiments (only one way to do that)
You can opt for only one condiment (there are 3 ways; a, b, or c)
You can opt for two condiments (there are 3 ways; ab, ac, or bc)
Or you can opt for all three condiments (only one way; abc)
Add these combinations up and you get 1 + 3 + 3 + 1 = 8

Technically what you've done is taken 4 different combinations of 3:
3 items chosen 0 at a time (3 choose 0)
3 items chosen 1 at a time (3 choose 1)
3 items chosen 2 at a time (3 choose 2)
3 items chosen 3 at a time (3 choose 3)

n choose k is can be shown with the following notation: [itex]_n C _k[/tex]
and is calculated with the following formula:

$$\frac{n!}{k!(n-k)!}$$

So, for the above example, we have:

$$_3C_0 = \frac{3!}{0!(3-0)!} = \frac{3!}{0! \times 3!} = \frac{6}{1 \times 6} = 1$$

$$_3C_1 = \frac{3!}{1!(3-1)!} = \frac{3!}{1! \times 2!} = \frac{6}{1 \times 2} = 3$$

$$_3C_2 = \frac{3!}{2!(3-2)!} = \frac{3!}{2! \times 1!} = \frac{6}{2 \times 1} = 3$$

$$_3C_3 = \frac{3!}{3!(3-3)!} = \frac{3!}{3! \times 0!} = \frac{6}{6 \times 1} = 1$$

We are looking for the sum of these combinations, so for any n>0 and 0<=k<=n, we have:

$$\sum_{k=0}^n _nC_k = \sum_{k=0}^n \frac{n!}{k!(n-k)!}$$

Now, assuming that we can opt for all 15 condiments (unlikely), we come up with a total of 32768 possible combinations.

Looking at the possibility of having "light" or "extra" options for 4 of the condiments, (say a, b, c, and d) we have for these particular condiments these options:
normal a
light a
extra a
normal b
light b
extra b
normal c
light c
extra c
normal d
light d
extra d

That's 12 options for those 4 condiments. Think of each of those 12 options as a different condiment with the restriction that you can't have more than one of the 3 choices for any given condiment (e.g. you can't have both "normal a" and "light a" or "light b" and "heavy b", etc.). This further complicates the calculation.

Ignoring these 4 condiments, we then have 11 to choose from, giving us:

$$\sum_{k=0}^{11} _{11}C_k = \sum_{k=0}^{11} \frac{11!}{k!(11-k)!} = 2048$$

Each of these 2048 options has the addition choice of adding some amount (normal, light, or heavy) of the remaining 4 condiments.

It turns out that there are 64 ways of choosing those condiments (counting choosing none). So, you have 64 ways to add the 4 "special" condiments to each of the 2048 options for the first 11 condiments. 2048 x 64 gives us 131,072 ways to make the burger.

17. Oct 5, 2010

### DrGreg

I don't think you have counted "choosing none". In my (much easier) method in post #12, I got 44 = 256. (64 is 43.)

18. Oct 6, 2010

### zgozvrm

Yes, I counted "choosing none," but I only counted 3 of the "special" condiments, and even then, I forgot to count the 63 possibilities of hamburgers having some combination of those 3 "special" condiments only (not using any of the other 11). Therefore, the total should have been 131,135.

The correct count should have been as follows:

For the 4 "special" condiments, we have:
a1 = a "normal" amount of condiment "a"
a2 = a "light" amount of condiment "a"
a3 = a "heavy" amount of condiment "a"
Also, we have b1, b2, b3, c1, c2, c3, d1, d2, and d3

There is the case that we choose none of the special condiments (1 case)
We can choose any one of the special condiments (12 cases) ---- [itex]_4C_1 \times _3C_1[/tex]
We can choose any 2: 54 cases ---- [itex]_4C_2 \times _3C_1 \times _3C_1[/tex]
Choose any 3: 108 cases ---- [itex]_4C_3 \times _3C_1 \times _3C_1 \times _3C_1[/tex]
Choose any 4: 81 cases ---- [itex]_4C_4 \times _3C_1 \times _3C_1 \times _3C_1 \times _3C_1[/tex]
(don't forget, that you can't choose combinations like: a1a2, a1b1b2, a1a2a3b2, etc.)

Total possible combinations of the special condiments: 1 +12 + 54 + 108 + 81 = 256
Although this is the same number that DrGreg came up with, [itex]4^4[/tex] has no meaning in this problem since we have 4 items with 3 states each.

So then we have 1 combination of no condiments, 2047 combinations of the 11 main condiments and 255 combinations of the 4 special condiments. Plus, we have 2047 x 255 = 521,985 ways to use some of the 11 main condiments, along with some of the 4 special ones

The grand total of combinations of condiments is therefore 1 + 2047 + 255 + 521,985 = 524,288

Last edited: Oct 6, 2010
19. Oct 6, 2010

### zgozvrm

Correction, DrGreg is right in his calculation ... I was looking at the combinations a different way. Both of our techniques are valid.