12 Toppings, 4 toppings per pizza, How many total?

[alec_tronn]

Homework Statement

You can order a pizza with up to four toppings (repetitions allowed) from a set of 12 toppings. The order of the toppings is unimportant. How many different pizzas can you order? (To clarify: this UP TO four toppings, so a completely empty pizza is fair game, as is a pizza with just 1 topping on it).

The Attempt at a Solution

I decided that there was 1 pizza with nothing on it, and 12 with one topping on it. Going from there, there are 12^{2}/2! ways to make a pizza with 2 toppings, 12^{3}/3! ways to make a pizza with 3 toppings, and 12^{4}/4! ways to make a pizza with 4 toppings. This is 1237.

A different attempt was made as follows:
How many pizzas are there with unique toppings?
12 choose 4 (all different toppings) + 12 choose 3 (3 different toppings and 1 empty spot) + 12 choose 2 (2 different toppings and 2 empty spots) + 12 choose 1 (1 different toppings and 3 empty spots) + 12 choose 0 (all empty)

How many pizzas are there with 2 identical toppings:
12 choose 3 (2 identical, 2 different) + 12 choose 2 (2 identical, 1 different, 1 blank) + 12 choose 1 (2 identical, 2 blank)

How many pizzas are there with 3 identical toppings:
12 choose 2 (3 identical and 1 different) + 12 choose 1 (3 identical and 1 blank)

How many pizzas are there with 4 identical toppings
12 choose 1 (all four identical)

How many pizzas are there with 2 duplicates:
12 choose 2 (2 identical and another 2 of a different type identical)

Add them all up, and you get 1248.

Both ways seem logically sound to me, but they're 11 pizzas off. Any ideas?

 

[Dick]

Why not just call the 'no topping' option a 13th topping choice. Doesn't that simplify the counting? Now there are C(13,1) to choose a single topping.

 

[alec_tronn]

I considered that. Using that method I tried (13 choose 1)^{4} (choosing 1 topping for each of your 4 spaces), and then divided that by 4! (because order isn't important) and I got a decimal (1190.0416666666666666666666666667). Am I doing that wrong?

 

[antiemptyv]

What if we simplified the problem? Suppose we were making a 2-topping pizza from 3 possible toppings (given the same conditions)? Say the toppings are 1, 2, and 3. We can list the possibilities pretty easily. By letting "0" be the null topping, we can have the following toppings choices: 00, 01, 02, 03, 11, 12, 13, 22, 23, 33.

Following the reasoning of your first argument, the number of these is 1 + 3 + 3^2/2!, but this is not an integer. This compensation for the overcount is not quite right. Do you see why?

(Sometimes thinking of a different, identically-solved problem helps: Counting the solutions to this is analogous to counting the number of ways of putting 4 indistinguishable "balls" into 13 distinguishable "boxes." Let each box represent a topping, and let a ball in a box represent the choice a topping. There are 13 boxes because one box represents choosing the null topping. This number is the number of 4-element "multisets" of a 13-element set.)

 

[alec_tronn]

Thanks!

Alright, using the ball\box analogy, I got:

All 4 in 1 box -> 13 choose 1
3 in 1, 1 in 1 -> (13 choose 1)*(12 choose 1)
2 in 1, 2 in another 1 -> 13 choose 2
2 in 1, 1 in 1, 1 in another 1 -> (13 choose 1)*(12 choose 2)
1 ball in each box for some 4 box -> (13 choose 4),

I add that all up and I get 1820, and entirely new answer. Did I do that right?

 

[Dick]

I get 1820 as well. I counted it like this. C(13,1)+C(13,2)*3+C(13,3)*3+C(13,4). The combinatorial parts should be pretty clear. It's C(13,2)*3 because once you pick a pair of types a and b, you can have either 3 of a and 1 of b, 1 of a and 3 of b, or 2 of both. Similarly for C(13,3). One of the three chosen ingredients occurs twice.

 

[antiemptyv]

yeah, that seems good. There's a generalization of the binomial coefficient--the multinomial coefficient that makes counting things like this simpler. (the hard part is deciding if it's the right approach!) It takes into account the overcount you initially were considering by dividing by the factorial of the number of times an element appears in your "multiset."

It looks like this: {n \choose k_1, k_2, \ldots, k_m}<br /> = \frac{n!}{k_1!\, k_2! \cdots k_m!}. Of course, when m=2, this is exactly the binomial coefficient. Anyway, it's a pretty useful tool. But using the multinomial coefficient for this particular problem is a little less straight-forward than just setting n=12, k=4, as one may do using the binomial coefficient for some other problem. Fun stuff.

 

[Dick]

Yeah, there's lots of ways to count. I usually try at least two to make sure I've got head screwed on right before I believe my answer.

 

[mgb_phys]

I think it has to be studied experimentally, I will send you the address to deliver them to.