0

Homer’s Pizza is advertising the following deal: • 2 pizzas • up to 3 toppings on each pizza • 7 toppings to choose from

Double or triple toppings are allowed. Two of same pizzas allowed. Arrangement of toppings does not matter.

What is the total number of possibilities for a pizza order in this deal?

Naruto
  • 31

2 Answers2

0

For the first ingredient on the first pizza you have 7 choices. Since double and triple toppings are allowed, you have 7 choices for the second and third topping. This yields 7*7*7 choices for the first pizza. For the second pizza you have the same choices(7*7*7). Since you are ordering 2 pizzas, the answer is (7*7*7) * (7*7*7), or 7^6.

If single topping and double toppings are allowed, then it is probably: (7 + 7*7 + 7*7*7) * (7 + 7*7 + 7*7*7)

Wayne
  • 1
  • This overcounts the possibilities. One pizza with three toppings gives you $7^3$ possibilities only if you consider each permutation of the same three toppings to be different. The problem statement says not to do that. And that is not the only way this overcounts the possibilities. – David K Nov 06 '18 at 04:53
0

"Up to three toppings" implies that it is permissible to order a pizza with two toppings, or one, or even with no toppings. We can handle these as separate cases, or we can invent an eighth choice of "topping," called "none," which can be selected as a single, double, or triple choice to reduce the number of actual toppings.

The number of ways to top a pizza is then the number of ways you can make exactly three selections from eight options with repeated selections allowed, but disregarding the sequence in which the selections are made. This is the number of $8$-tuples of non-negative integers with the sum $3$, where the number at the $i$th position in the $8$-tuple says how many times we select the $i$ topping option. This is a well-known problem in combinatorics, equal to the number of ways you can arrange three identical items in eight labeled bins, solvable by a method often called "stars and bars" (see Stars and Bars Derivation for example). The number of $k$-tuples with sum $n$ is $\binom{n+k-1}{k - 1} = \binom{n+k-1}{n}.$ For the toppings of a single pizza we have $k = 8$ and $n = 3,$ so the number of ways to top a pizza is $$ \binom{3+8-1}{3} = \binom{10}{3} = \frac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1} = 120.$$

For two pizzas, presumably an order consisting of one triple mushroom pizza and one triple onion pizza is the same as one triple onion and one triple mushroom, so the answer is not simply $120^2.$ You can consider separate cases for two different pizzas and for both pizzas the same, or you can consider this a problem of the number of ways to make exactly $2$ selections (with repetition allowed but disregarding the sequence of selections) from $120$ options, to which we can again apply the formula $\binom{n+k-1}{n}$ with $k = 120$ and $n = 2,$ $$ \binom{2 + 120 + 1}{2} = \binom{121}{2} = \frac{121\cdot 120}{2} = 7260.$$

David K
  • 98,388