10 Ingredients to choose from for a sandwich. Total ways

combinationscombinatorics

If, at the restaurant, it is possible to have on a pizza any combination of pepperoni, mushrooms, sausage, green peppers, onions, anchovies, salami, bacon, olives, and ground beef ($10$ different ingredients). How many different combinations exist?

I assumed you can't pick an ingredient more than once, so my thinking was this:

I have $11$ choices for the first ingredient (I included the choosing of no topping), $10$ choices for the second ingredient, $9$ for the third, etc. So the total number of ways I can make a pizza is $11!$ but the book says the total number is $2^{10}$. Why?

Best Answer

There are $10$ possible toppings on a pizza, and each of these toppings individually has $2$ different possibilities: on the pizza, or off the pizza. Hence the total number of possible pizzas is $2^{10}$.

I like to visualize it as $10$ "slots", one for each topping, and the number of options each individual topping can have - i.e. $2$, because each individual topping is a simple "yes" or "no" - goes into each slot. Then all $10$ of those $2$'s get multiplied to arrive at the final answer of $2^{10}$.

Notice this also counts the pizza with no toppings at all: it is simply the option where you have chosen "no" for every one of the $10$ options.

You would use factorials if you wanted to count permutations of toppings - but, in this case, the order you put the toppings on the pizza does not matter. You get the same pizza (presumably) whether you put the pepperoni on first or the mushrooms on first.