A pizza deal: for one low price you get two pizzas, each with up to 5 toppings chosen from 11.

If we allow "doubling up" in this manner, we just have to consider the
partitions of 5,4,3,2,1, and 0 and add up the corresponding combinations:

part.        combos

5        11
41        110
32        110
311        495
221        495
2111        1320
11111        462

4        11
31        110
22        55
211        495
1111        330

3        11
21        110
111        165

2        11
11        55

1        11

0        1        ( The cheese stands alone )

For a total of 4368 combinations,
and 4368*4369/2 = 9541896 pizza pizza's.

-- Lew Mammel, Jr. <lew@cbnewsd.cb.att.com>

This is a very nice puzzle; so far I've seen one incorrect answer and
one brute-force answer.  Here's one that's neat and easily
generalized. ...

There are (11 + 5 choose 5) = 4368 ways to top a pizza with up to 5
out of 11 toppings.  So there are 4368*(4368 + 1)/2 = 9541896
possible choices of two pizzas.

If you insist on *exactly* 5 toppings (Little Caesar's apparently
doesn't), then there are (10 + 5 choose 5) = 3003 way to top one
pizza, and 3003*(3003 + 1)/2 = 4510506 choices of two pizzas.

Either answer is a lot more than the advertised 1048576 choices.

I'm going to give a rather verbose explanation since I want this to be
accessible to high school students.

The first question is how many ways you can select up to 5 toppings
out of 11 with repetition allowed.  The answer is that there are
(m + n choose n) ways to choose up to n toppings out of m with
repetition allowed.

To see why, consider any one of the possible combinations, for example
anchovy, double pepperoni, and sausage.  Make a long row of boxes on a
sheet of paper and run through the list all the m available toppings in
alphabetical order.  Starting at the leftmost box, for each topping,
if the topping occurs k times in your choice, mark the first k empty
boxes with an X, then write the name of the topping in the next empty
box.  So you mark:

    X    anchovy            for single anchovy topping (k = 1)
    X       X    anchovy    for double anchovy (k = 2)
 anchovy                    for no anchovy (k = 0)

After you've listed all m toppings, you have at most n boxes with X's
in them.  If you have fewer than n X's, mark some more empty boxes
with X until you have exactly n X's.

Now you have a row of m + n boxes with n of them marked with X.  Each
combination you could order produces a different set of m + n boxes;
on the other hand, if you take m + n boxes and mark any n of them with
X, you uniquely determine a combination you could have ordered (just
fill in the toppings in the empty boxes in alphabetical order).  So
the number of possible combinations of toppings is the same as the
number of ways to mark n boxes out of m + n with X's, that is,
(m + n choose n).

In our case, m = 11 and n = 5, so the number of combinations is
(16 choose 5) = 16*15*14*13*12/5! = 4368.

If you insist that *exactly* n toppings must be selected, then there
can be no leftover X's to mark after the name of the last topping, so
the last box always has a topping name in it, and every choice is
uniquely determined by which of the first m + n - 1 boxes have X's in
them.  So the number of choices is (m + n - 1 choose n).  In our
case, we get (15 choose 5) = 3003 combinations.

Now if you have two pizzas, and each can be topped in p different
ways, then the number of possible ways to choose two different pizzas
is (p choose 2) = p*(p - 1)/2, and the number of ways to choose two
identical pizzas is p.  So the total number of choices is

   p + p*(p - 1)/2 = p*(p + 1)/2.

-- David A. Karr <karr@cs.cornell.edu>

A problem isomorphic to this one actually came up in a high school algebra
class back when I was a student teacher.  The teacher had posed on a test
the following problem:

        How many terms are in the expansion of (a+b+c+d)^7?

The teacher intended the students to consider, for example, aaabccd and aabaccd
as two separate terms, so she was looking for the answer 4^7.  But all of the
students understood the problem as meaning how many terms after combining the
ones that are just rearrangements of each other, as in

        (a+b)^2 = a^2 + 2ab + b^2

which is three terms after combining equal ones.  None of the students could
figure this out.  I went home and came up with a recurrence relation that
could (by using hairy post-calculus techniques) be solved to give the correct
answer, but David Karr's method with the Xs and separators also works fine
for this problem.

-- Brian Harvey <bh@anarres.CS.Berkeley.EDU>

My answer depends on whether or not we consider a pizza with a topping
chosen more than once (ex: double pepperoni) the same as if it were only
chosen once.  I assume the first way.

(It may be hard to fathom that a 5-topping pizza with pepperoni chosen
for all 5 toppings is different from a 4-topping pizza with pepperoni
chosen for all 4 toppings because there's a different amount of
pepperoni on it {yeah right - like the people who work there are really
going to count}  {although maybe they'd use a measuring cup}, but it
makes the problem more fun.)  :)

Given that, I get an answer different from all the numbers I've seen
above.  My answer combines a couple of points mentioned in earlier
messages.  Here goes.

1) First ->  How many combinations exist for an up-to-5 topping pizza
             (chosen from 11 toppings)

     Pizzas where customer chooses to use all 5 of his/her
                        toppings choices
     ----------------------------------------------------
As Mark Meyer (mmeyer@m2.rts.dseg.ti.com) mentioned in his 11/10/93
message, "One can get 5 toppings, but they don't have to be distinct."
So a customer can choose this: Pepperoni, Sausage, Mushroom, Pepperoni,
Mushroom.  (Little Caesar's will let you choose double, triple or even
quadruple of one topping.)  The underlying assumption I make in solving
this part is that those are all different combinations.  (I know it
could just as well be argued that they shouldn't be considered separate.)

Case 1
------
So, a 5-topping pizza with 5 single toppings is C(11,5) = 462.

Case 2
------
A 5-topping pizza with 1 double topping, and 3 singles is C(11,4)=330
        Ex: Pepperoni, Pepperoni, Sausage, Mushroom, Olives
             11      *    10           *    9     *    8     /      4
      (double topping)  (single)   (single)   (single)

Case 3
------
A 5-topping pizza with 2 double toppings, and 1 single topping
        Ex: Pepperoni, Pepperoni, Mushrooms, Mushrooms, Sausage
                C(11,3) = 165

Case 4
------
A 5-topping pizza with 1 triple topping, and 2 single toppings
        Ex: Pepperoni, Pepperoni, Pepperoni, Mushrooms, Sausage
                C(11,3) = 165

Case 5
------
A 5-topping pizza with 1 triple topping, and 1 double topping
                C(11,2) = 55

Case 6
------
A 5-topping pizza with 1 quadruple topping, and 1 single topping
                C(11,2) = 55

Case 7
------
A 5-topping pizza with 1 quintuple {is that how you spell it} topping
                C(11,1) = 1

Add all the cases together and we get 462+330+165+165+55+55+1 =
1243 possible pizzas where all 5-topping choices are used up.

     Pizzas where the customer chooses to use only 4 of his/her
                           topping choices
     -----------------------------------------------------------
Application of the same methodology as above should result in this
addition and answer:  330+165+55+55+11 = 616

     Pizzas where the customer chooses to use only 3 of his/her
                           topping choices
     ----------------------------------------------------------
Application of the same methodology as above should result in this
addition and answer:  165+55+11 = 231

     Pizzas where the customer chooses to use only 2 of his/her
                           topping choices
     ----------------------------------------------------------
Application of the same methodology as above should result in this
addition and answer:  55+11 = 66

        Pizzas where the customer chooses only 1 topping
        ------------------------------------------------
Application of the same methodology as above should result in this
answer:  11

           Pizza where the customer chooses no topping
           -------------------------------------------
There is only 1 possibility (a plain pizza).

Then, adding all those final possibilities together.
        1243+616+231+66+11+1 = 2168 !
                               ----

If we accept 2168 as the number of possible combinations that can be
ordered for the first and for the second pizza, we now must calculate
the number of possible 2-pizza combinations.  My rationale on this
next part leads to the same formula that David Karr (karr@cs.cornell.edu)
mentioned in his 11/12/93 posting (although I didn't understand the
"n choose m" terminology {not to say it was a bad or wrong method at
all}).

First, consider only those situations where the customer chooses
2 pizzas which are non-identical to each other.

That means there are 2168 possibilities for the first pizza and
2167 possibilities left for the second pizza.  Since order is not
important (we in fact want to avoid counting X,Y and Y,X as two
distinct situations since as people mentioned before, it shouldn't
matter in which order the pizza's are brought in the door by the
delivery person), we must use the familiar combination formula (rather
than the permutation formula which takes order into account).

So we have   C(2168,2)  =  2168 * 2167 / 2 = 2,349,028

The next question is how many situations exist where both pizzas have
the exact same things (so that the pizzas are duplicates of each other).
Well, for each possible way that the first pizza could be, there is
only 1 choice for the second that would satisfy this.  So there are
2168 situations where the 2 pizzas are exactly the same.

Add the # of situations where the pizzas are different to the # of
situations where they are the same and you get

    2,349,028 + 2,168 = 2,351,196
                        ---------

-- Mark Dranoff <dranoff@sunburn.ec.usf.edu> [Editor: the posting is
   signed by Mark Schneider <mas@elm.circa.ufl.edu>, who is also its
   Sender.]

In article <2c3aat$67u@suntan.eng.usf.edu> dranoff@sunburn.ec.usf.edu.
(Mark Dranoff (EE)) writes:
>So, a 5-topping pizza with 5 single toppings is C(11,5) = 462.

True.

>A 5-topping pizza with 1 double topping, and 3 singles is C(11,4)=330

False.  Yes, you choose 4 out of 11 toppings, but then you have 4
choices as to which of those gets doubled.  So there are really
1320 possibilities, 990 more than you counted.

>A 5-topping pizza with 2 double toppings, and 1 single topping
>                C(11,3) = 165

False.  You choose 3 toppings, but then you have 3 different choices
of which two out of the three get doubled.  So the answer is 495,
which is 330 more than you counted.

>A 5-topping pizza with 1 triple topping, and 2 single toppings
>                C(11,3) = 165

Again you neglected to multiply by 3, so you undercounted by 330.

>A 5-topping pizza with 1 triple topping, and 1 double topping
>                C(11,2) = 55

Need to multiply by 2 this time; you undercounted by 55.

>A 5-topping pizza with 1 quadruple topping, and 1 single topping
>                C(11,2) = 55

Undercounted by 55 again.

>A 5-topping pizza with 1 quintuple {is that how you spell it} topping
>                C(11,1) = 1

No, C(11,1) = 11.  Undercounted by 10.

>Add all the cases together and we get 462+330+165+165+55+55+1 =
>1243 possible pizzas where all 5-topping choices are used up.

You added wrong.  The sum is 1233.  (Or did you actually have 11
instead of 1, and the 1 is just a typo in two places?)
Your total undercount was 990 + 330 + 330 + 55 + 55 + 10 = 1770.
Now 1233 + 1770 = 3003 = C(15,5), which is exactly what I said the
answer should be:  C(m + n - 1,n) for m = 11, n = 5.

(The phrase "n choose m" in my article was simply the way I was taught
to pronounce "C(n,m)."  Sorry if this caused a misunderstanding.)

... and so forth.  The actual numbers, using the formula C(m + n - 1,n):

For 4 toppings:  C(14,4) = 1001.
For 3 toppings:  C(13,3) = 286.
For 2 toppings:  C(12,2) = 66.
For 1 topping:   C(11,1) = 11.
Plain pizza:     C(10,0) = 1.

Grand total:     C(16,5) = 4368.  You can check that this is the sum.

-- David A. Karr <karr@cs.cornell.edu>

In article <CGpG18.o2@twisto.eng.hou.compaq.com> costley@solo.eng.hou.compaq.com
(Brett Costley) writes:
>From a pizza commercial:
>
>There is a pizza deal.  For one low price you get two pizzas, each
>with up to 5 toppings.  The toppings do not have to be the same on
>each pizza.  There are supposedly 1048576 possible choices.  How
>many toppings are there to choose from?

17.  The people who wrote the commercial miscalculated the resulting
number of combinations.

Seriously, we just went through this question twice.  There are 11
toppings, so (2^11)/2 = 1024 ways to select up to (11 - 1)/2 = 5 of
them barring multiple servings of one topping on the same pizza (i.e.,
double pepperoni is not counted), and *if* you can always tell the two
pizzas apart even when they have the same topping, there are
1024^2 = 1048576 possibilities.

But Little Caesars apparently does distinguish double pepperoni from
single, so you have (16 choose 5) = 4368 choices for one pizza.
(Why (16 choose 5) and what does that mean, anyway?  Read last week's
postings!)

But they also have two pizza shapes, round and square, and unless the
commercial says you have to get one of each, you could get two round
pizzas, for 4368*(4368 + 1)/2 = 9541896 choices.  Or you could get two
square pizzas, for another 9541896 choices.  Or you could get one of
each, for 4368*4368 = 19079424 choices.  A total of 38163216 choices,
or nearly 36.4 times the advertised number.  Is that enough for you?

ObPuzzle: Suppose you have *fewer* than 11 possible toppings, but you
are allowed to order two pizzas with up to 5 toppings on each.  Is it
possible for there to be 1048576 pizza combinations and no more,
counting single, double, triple, quadruple, and quintuple servings of
one topping as different combinations?

-- David A. Karr <karr@cs.cornell.edu>

[ Editor: no answer to the ObPuzzle was found in the collected
postings. ]