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

• alec_tronn
In summary, there are 1820 different pizzas that can be ordered with up to four toppings from a set of 12 toppings. This includes options for no toppings, one topping, two toppings with duplicates, two toppings with one being blank, three toppings with duplicates, and four identical toppings. Different approaches can be taken to count the possible combinations, such as using the multinomial coefficient.
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?

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.

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?

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.)

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?

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.

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} = \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.

Last edited:
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.

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

## 1. How many pizzas do I need to order to have exactly 12 toppings?

You will need to order 3 pizzas to have exactly 12 toppings, as each pizza can have up to 4 toppings.

## 2. What is the maximum number of pizzas I can order with a total of 12 toppings?

The maximum number of pizzas you can order with a total of 12 toppings is 3, as each pizza can have up to 4 toppings.

## 3. Can I have more than 4 toppings on one pizza?

Yes, you can have more than 4 toppings on one pizza. Each pizza can have up to 4 toppings, but you can order multiple pizzas to reach a total of 12 toppings.

## 4. How many different combinations of 4 toppings can I have on each pizza?

There are 12 different combinations of 4 toppings that you can have on each pizza. This is because 4 toppings can be arranged in 12 different ways.

## 5. Can I have the same topping on multiple pizzas?

Yes, you can have the same topping on multiple pizzas. Each pizza can have up to 4 toppings, so you can have the same topping on each of the 3 pizzas to reach a total of 12 toppings.

• Calculus and Beyond Homework Help
Replies
6
Views
9K
• Calculus and Beyond Homework Help
Replies
2
Views
568
• Calculus and Beyond Homework Help
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
3K
• Calculus and Beyond Homework Help
Replies
4
Views
225
• Calculus and Beyond Homework Help
Replies
5
Views
477
• General Math
Replies
14
Views
2K
• Precalculus Mathematics Homework Help
Replies
1
Views
813
• Quantum Physics
Replies
8
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
3K