# Hot dog combinatorics

A hot dog stand has 12 different toppings available. How many different kinds of hot dogs can be made, assuming the order of the toppings does not make a difference. I believe the correct answer is 882050, with the maximum varieties per number of toppings selected being 665280 when there six toppings. I am also not sure about how to create a formula that would arrive at this result.

• I doubt that 882,050 hot dogs actually fit in the stand ;) Jul 30, 2015 at 19:40
• The Dalai Lama goes up to a hotdog vendor in central park and says "Make me one with everything". Jul 31, 2015 at 7:27
• After the vendor gives him the hotdog the Dalai Lama hands the vendor a $20 bill. The vendor takes the 20 and does nothing. After a few minutes the Dalai Lama asks "Where's my change". The vendor replies "Ah, change comes from within". (rimshot, ducks) Jul 31, 2015 at 7:29 • @johannesvalks They don't have to fit in the stand... Jul 31, 2015 at 8:55 ## 5 Answers For each topping you can choose to include it or not include it. This results in$2^{12}=4096$different kinds of hot dogs. For each topping you can decide to use it or not to use it. So for each topping you have$2$ways. Thus in total you have$2^{12}$ways. It's not necessarily a yes or no question on each topping. For each topping, I would make 4 different 'states' • none • regular • extra • easy$4^{12}=16,777,216\$ individual hot dogs, which would definitely not fit in the stand. You could refine it more to have different standardized volumes of topping, but then you'd just get ridiculous. You could further confuse the issue by counting the bun as being a topping, because you wouldn't really have easy or extra bun, hun.

• A bit over the top, your hot dog... ;-] Jul 30, 2015 at 23:44

Also, you can view it like this: $$\sum_{k=0}^{12} C_{12,k} = \sum_{k=0}^{12} \binom{12}{k} = 4096$$

i.e. for each number k of toppings, you get k-combinations between those elements, from the starting 12. We are using combinations without repetition because order of selection does not matter.

Numerically: $$\sum_{k=0}^{12} \binom{12}{k} = 1 + 12 + 66 +220 +495 +792 +924 +792 +495 + 220 +66 +12 +1 = 4096$$

The vendor can make uncountably many different kinds of hot dogs but varying the amount of one single topping, if the amount can be expressed as a real number (e.g. weight).