\problemdata      
        {counting-15} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {S95 PS7} % Source (if known)
        {S02 CP8F; S00, PS7} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\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 Harvard student who had figured out that
$(2^{11})^2 = 4,194,304$.  Unfortunately, this number $(2^{11})^2$ is
actually wrong. In how many can you really choose toppings for the two
pizzas?

\solution{The first thing to understand is where the $2^{11}$ came
from. The number of ways to choose different toppings for one pizza is
all the possible 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).

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