In how many ways can 20 different pizza toppings be chosen from 24 available toppings

Iceberg

A task is the tip of a learning iceberg. There is always more to a task than is recorded on the card.    

The first question students are likely to ask is Can we have more than one serve of each topping on a pizza?. The card is deliberately left open so this is likely to happen because often a mathematician has to define the limits of their problem before they can begin. In this case there are going to be significantly fewer solutions if you are not allowed to repeat a topping, so using that rule might be a good place to start.

The card also says the pizzas could have up to four toppings, which means they could have zero toppings [cooked pizza dough is quite nice!], one topping, two toppings, three toppings or four toppings. So, if we use Y, G, W & R to stand for the various toppings, the possibilities are:

UP TO 4 TOPPINGS

Toppings Used	Possible Pizzas	No. of Pizzas
0	Base only	1
1	Y, G, W, R	4
2	YG, YW, YR, GW, GR, WR	6
3	YGW, YGR, YWR, GWR	4
4	YGWR	1
	Total of pizzas	16

And that answers both questions in the challenge. There are 16 pizzas and we know we have found them all because we have broken the problem into smaller parts and considered every possible case.

Before reading further, you might divert to inspect Oliver's Journal Record for this problem, which is part of an article from Ashburton Primary School, describing what happened when the teachers began to expect and value the parts of a mathematician's work related to recording and publishing. [Click on the photos of Oliver's work to enlarge them.]

Extensions

• What happens if we are limited to a different number of toppings?

More toppings would give more pizzas, so perhaps it is sensible to consider fewer toppings first.

UP TO 0 TOPPINGS

Toppings Used	Possible Pizzas	No. of Pizzas
0	Base only	1
	Total of pizzas	1

UP TO 1 TOPPING

Toppings Used	Possible Pizzas	No. of Pizzas
0	Base only	1
1	Y	1
	Total of pizzas	2

UP TO 2 TOPPINGS

Toppings Used	Possible Pizzas	No. of Pizzas
0	Base only	1
1	Y, G	2
2	YG	1
	Total of pizzas	4

UP TO 3 TOPPINGS

Toppings Used	Possible Pizzas	No. of Pizzas
0	Base only	1
1	Y, G, W	3
2	YG, YW, GW	3
3	YGW	1
	Total of pizzas	8

If at this stage we put the previous result into the sequence:

UP TO 4 TOPPINGS

Toppings Used	Possible Pizzas	No. of Pizzas
0	Base only	1
1	Y, G, W, R	4
2	YG, YW, YR, GW, GR, WR	6
3	YGW, YGR, YWR, GWR	4
4	YGWR	1
	Total of pizzas	16

We might notice a few things that help us predict the table for up to 5 toppings and beyond, without needing to make the pizzas.

• The total is a sequence of powers of 2.
• There will always be only one way to make the 0 toppings and all toppings pizzas.
• The number of 1 topping pizzas will always be the same as the number of toppings available.
• The number of pizzas for one less than the all toppings pizza will always be the same as for the one topping pizza, because it could be made by subtraction from the all toppings pizza instead of addition to the base. That is, beginning with the all toppings, the only way to make the pizzas with one less is to take off a single topping and that can only be done in the same number ways as there are toppings.

So using these observations helps us complete some of the table for up to 5 toppings - Y, G, W, R, B [for black olives perhaps].

UP TO 5 TOPPINGS

Toppings Used	Possible Pizzas	No. of Pizzas
0	Base only [as always]	1
1	Always the same as the number of toppings, so...	5
2
3
4	Subtract each of the toppings from the all toppings to get...	5
5	All toppings on, so...	1
	The pattern suggests ... Total of pizzas	32

Looking back at the previous data also suggests that there is an 'up and down' symmetry in the last column of each table and that the two missing numbers should be the same. Also we know the totals we have plus the missing ones must equal 32. The totals we have so far sum to 12. We need 20 more, so each missing number must be 10 and the table is:

UP TO 5 TOPPINGS

Toppings Used	Possible Pizzas	No. of Pizzas
0		1
1		5
2		10
3		10
4		5
5		1
	Total of pizzas	32

However, the 10s are really only an hypothesis and so need to be checked another way. Students can be challenged to make them to prove that there are exactly 10 in each case. Or, they might reason something like this:

• There are 5 flavours Y, G, W, R, B.
• Choose 1 to be on the pizza, say Y, then there are only 4 toppings that can be paired with it.
• There are no other ways to use Y, so no more pizzas can include it.
• Choose the next one to be on the pizza, G, then there are only 3 toppings that can be paired with it, because G has already been paired with Y.
• There are no other ways to use G, so no more pizzas can include it.
• Choose the next one to be on the pizza, W, then there are only 2 toppings that can be paired with it, because W has already been paired with G and Y.
• There are no other ways to use W, so no more pizzas can include it.
• Choose the next one to be on the pizza, R, then there is only 1 topping that can be paired with it, because R has already been paired with W and G and Y.
• There are no other ways to use R, so no more pizzas can include it.
• Choose the next one to be on the pizza, B, then there are no other toppings that is hasn't been paired with already, so there are no more pizzas to make with it.

So the total number of 2 toppings pizzas from 5 ingredients is 4 + 3 + 2 + 1 = 10. A similar argument about subtracting from the five 4 toppings pizzas must also produce 10 pizzas. Try it.

Pascal's Triangle

If the No. of Pizzas columns are separated out and arrange in rows like this:

						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1

which is known as Pascal's Triangle [see Task 144, Pascal's Triangle in Asia], more patterns emerge. For example each number within the triangle is the sum of the two above it and this allows us to easily calculate the pizzas for up to 6 toppings.

						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1
1		6		15		20		15		6		1

And, not surprisingly, these numbers sum to a power of 2, so there are 64 pizzas that can be made with up to 6 toppings.

There are probably a dozen more investigations linking this triangle and the pizza problem, for example:

• What happens if we make pairs from the maximum toppings used number and the total pizzas number ... [0, 1] [1, 2] [2, 4] etc... and explore their graph?
• Looking backwards through the pattern of pizza totals suggests that 20 = 1
• The outside diagonals in either direction are 1. Why?
• The next diagonals are the natural numbers. Why?
• The next diagonal is the triangle numbers. Why and how do they relate to the natural numbers?
• What other patterns can be found in the triangle?

But perhaps enough is enough.

But we could return to the original assumption that toppings can't be repeated and ask what happens if you are allowed to use multiple serves of the same topping. How many pizzas can be made then?

No, enough is enough!

Whole Class Investigation

Tasks are an invitation for two students to work like a mathematician. Tasks can also be modified to become whole class investigations which model how a mathematician works.    

It is easy to set the context for this lesson by discussing how pizzas are made and the students' experiences with pizza shops. Highlight that in the shop the chef first gets a base and then slides it along a set of tubs that each have a toppings. You can choose to have or not have the various toppings. Pairs of students then set up their pizza shop with counters, tiles or blocks in colour piles across the top of their table. The bases are easy to make by folding, creasing and tearing paper. An A4 piece of paper can quickly supply 8 bases, 16 if each student in the pair folds, creases and tears one piece. Alternatively you might like to print this page of 6 pizza bases.

Explain that you aren't really trying to recreate a full pizza shop, but rather the same idea in the home kitchen so the kids can make pizzas for the tea. That allows the number of toppings to be limited and your class will easily accept that before they started you asked your children to guess how many different pizzas they would be able to make. That's what maths teachers do! Encourage your class to make the same guess. Now they want to find out which guess is correct and so the investigation begins. The iceberg notes above allow you to guide the investigation to whatever level of success is appropriate for the class and individuals.

For more ideas and discussion about this investigation, open a new browser tab [or page] and visit Maths300 Lesson 74, Pizza Toppings, which also includes an investigation guide with answers and discussion. The guide highlights some of the extensions above and adds suggestions for senior classes which link the task to coefficients in the expansion of [1 + x]t, where t is the number of toppings available, and developing and proving formulas, such as the link between the natural and triangle numbers, perhaps by Mathematical Induction.

How many ways can Max Select 3 toppings from 10 available toppings for his pizza?

How many ways can Rudy choose 5 pizza toppings from a menu of 20 toppings?

How many different pizzas can be made with 12 toppings?

How many possibilities can you have if you pick 5 pizza toppings out of 12?