5
$\begingroup$

You are ordering two pizzas. A pizza can be small, medium, large, or extra large, with any combination of 8 possible toppings (getting no toppings is allowed, as is gettting all 8). How many possibilities are there for your two pizzas?

Would it be ${\large[}4{\large[}{8\choose8}+{8\choose7}+{8\choose6}+{8\choose5}+{8\choose4}+{8\choose3}+{8\choose2}+{8\choose1}+{8\choose0}{\large]}{\large]}^2$

$\endgroup$
  • $\begingroup$ You forgot to include ncr(8,0), since getting no toppings is allowed. $\endgroup$ – Zelzy Nov 25 '14 at 18:22
  • $\begingroup$ Also, $ncr(x,0) + ncr(x,1) + ... + ncr(x, x-1) + ncr(x,x) = 2^x$ for non-negative integer values of $x$. (And possibly others, I don't actually know.) $\endgroup$ – Zelzy Nov 25 '14 at 18:23
6
$\begingroup$

You are correct if the order you get your pizzas matters. The stuff inside the outer square brackets (which equals $4 \cdot 2^8=1024$) is the number of single pizzas. It seems more likely that getting pizza A and then B is the same as getting B and then A. In that case you have to divide the cases of disparate pizzas by $2$, so there would be $1024$ (ways to get two the same) + $\frac 12\cdot 1024 \cdot 1023$ (ways to get two different).

You can save yourself computing all the $8 \choose n$'s by noticing that you have eight binary choices to make, one for each topping. You can make them in $2^8$ ways, so that gives the sum of all the $8 \choose n$'s

$\endgroup$
2
$\begingroup$

Let $i$ be the number of toppings you wish to include on your pizza, where $0 \leq i \leq 8$.

Choosing one pizza could be calculated as follows, $$4\sum\limits_{i=0}^8 {8\choose i} = 4\cdot2^8$$

To calculate the number of possibilities, I will count the number of ways in which you can have the same pizza plus the number of ways in which you can have two different pizzas:

Possibilities for choosing the same pizza is equal to the number of different possibilities for one pizza, that is $$4\sum\limits_{i=0}^8 {8\choose i} = 4\cdot2^8$$

Counting the possibilities for two different pizzas as follows, $$\frac{\Bigg[4\sum\limits_{i=0}^8 {8\choose i}\Bigg]\cdot \Bigg[\Bigg(4\sum\limits_{i=0}^8 {8\choose i}\Bigg)-1\Bigg]}{2}$$

$$= \frac{(4\cdot 2^8)\cdot(4\cdot 2^8 -1)}{2}$$

You're dividing by two since the order in which you pick the pizzas are not relevant.

In total, that gives you $$(4\cdot 2^8) + \frac{(4\cdot 2^8)\cdot(4\cdot 2^8 -1)}{2} = 524800$$ possibilities for two pizzas.

$\endgroup$
  • $\begingroup$ You're right, I overlooked that. Thanks for pointing that out. $\endgroup$ – Kermit the Hermit Nov 25 '14 at 18:58
  • $\begingroup$ @RossMillikan I fixed the error, thank you for your assistance. $\endgroup$ – Kermit the Hermit Nov 25 '14 at 19:31
1
$\begingroup$

there are 4 possible choices for pizza sizes

and the different combinations of all pizza toppings is the power set of 8 which is $2^8$

so the amount of possibilities is $4 \times 2^8$ for one pizza

the combinations for two pizzas would be ($4 \times 2^8)^2$ this is equivalent to your answer

$\endgroup$
  • $\begingroup$ Should it be ($4 \times 2^8 \times 4)^2$ to include for the scenario where there are 0 toppings? $\endgroup$ – larrysummersstatistics Nov 25 '14 at 18:28
  • 1
    $\begingroup$ no,there are $2^8$ elements in the power set so it would already be accounted for as the power set contains all subsets of the set of 8 toppings $\endgroup$ – Peter A Nov 25 '14 at 18:30
1
$\begingroup$

Note that this is problem 14 in chapter 1 of Introduction to Probability by Blitzstein and Hwang.

The problem amounts to sampling with replacement where the order doesn't matter, which is similar to problem 13 in and the hint there (use Bose Einstein) applies here too. This is also known as the "stars and bars" method.

Imagine an order form with $4 \times 2^8$ = 1024 columns for each distinct kind of pizza. With 2 pizzas there are $\binom{1024+2-1}{2}$ = $\binom{1025}{2}$ unique orders.

$\endgroup$
  • $\begingroup$ I don't understand the downvote? $\endgroup$ – rsp Apr 23 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.