\problemdata
{counting}
{pizza}
{toppings}

%source: spring00 ps7-5
% source: spring95 ps7
% topic: basic combinatorics, stars and bars
\begin{problem} A pizza house is having a promotional sale. Their commercial
reads:
\begin{quotation}\noindent
Buy $2$ large pizzas at the regular price, and get up to $11$ different
toppings for each pizza absolutely free.  That's $4,194,304$ different
ways to design your order!
\end{quotation}

\iffalse
 $\displaystyle \left( \sum_{k=0}^{11}\binom{11}{k} \right)^2
= \displaystyle \left(2048 \right)^2 = 4,194,304$\fi

The ad writer was a former MIT student who had figured out that
$(2^{11})^2 = 4,194,304$.  Unfortunately, this was a student who got a
\textbf{B-} in 6.042, and the number $(2^{11})^2$ is actually wrong.  In
how many can you really choose toppings for the two pizzas?

\solution{The number of ways to choose different toppings for one pizza
is the number of subsets of the set of 11 toppings, which is $2^{11}$.
However, when the student says that there are $(2^{11})^2$ different ways
to choose toppings for two pizzas, he is making the mistake of counting
the combination ``one mushroom and anchovy pizza, and one green-pepper
pizza" as different from the combination ``one green-pepper pizza and one
mushroom and anchovy pizza ."  (At least he knew enough not to count a
mushroom and anchovy pizza as different from an anchovy and mushroom
pizza---that's why he got a \textbf{B-} and not a \textbf{C}.)

The right solution is
\[
2^{11}+\binom{2^{11}}{2} = 2,098,176,
\]
namely, the number of ways to choose the same toppings for both pizzas
plus the number of ways to choose $2$ pizzas with different sets of
toppings.}

\end{problem}