The multiplication principle

What you will be able to do

• count the outcomes of a choice made in stages, without listing them all;
• draw a tree diagram for a small count, and see the product in it;
• count with repetition allowed, and with repetition not allowed;
• fill places one by one, such as the digits of a code or the strips of a flag.

Counting without listing

Neel packs for a school trip. He has $3$ shirts, white, blue and green, and $2$ pairs of trousers, black and grey. How many different outfits of one shirt and one pair of trousers can he wear?

You could list them all: white with black, white with grey, blue with black, and so on. A tree diagram lists them in order. It branches once for the shirt, and then once more for the trousers.

There are $6$ ends to the tree, so there are $6$ outfits. Look at how the tree is built. Each of the $3$ shirts has $2$ branches after it. So the number of ends is $3 \times 2 = 6$.

Listing works for $6$ outfits. It does not work for a million number plates. We need a rule that counts without listing.

The multiplication principle

The fundamental principle of counting. Suppose one event can happen in $m$ different ways, and after it a second event can happen in $n$ different ways. Then the two events, one after the other, can happen in $m \times n$ ways.

The rule extends to any number of stages. With $m$, $n$ and $p$ ways for three events in turn, there are $m \times n \times p$ ways in all.

Add $2$ pairs of shoes to Neel's bag. Each of his $6$ outfits can go with either pair, so he now has $3 \times 2 \times 2 = 12$ outfits.

The rule needs one condition. The number of ways for the second stage must be the same, whatever happened at the first stage. In the tree, every branch must split into the same number of new branches.

Repetition allowed, or not

A mobile phone asks for a $4$-digit PIN. Each digit is one of the $10$ digits $0$ to $9$.

• Digits may repeat. Each of the four places has all $10$ choices. There are $10 \times 10 \times 10 \times 10 = 10000$ PINs.
• No digit may repeat. The first place has $10$ choices. Once it is used, the second place has $9$, then the third $8$ and the fourth $7$. There are $10 \times 9 \times 8 \times 7 = 5040$ PINs.

So the words "with repetition" and "without repetition" change the count a great deal. Read them carefully in every question.

Filling places one by one

Many counting questions ask you to fill a row of places. Draw a box for each place. Write in each box the number of ways to fill it, and multiply.

Example. A flag has three horizontal strips, each of a different colour. There are $5$ colours to choose from. How many different flags can be made?

1. The top strip. Any of the $5$ colours: $5$ ways.
2. The middle strip. Any colour except the top one: $4$ ways.
3. The bottom strip. Neither of the two colours used: $3$ ways.

So there are $5 \times 4 \times 3 = 60$ flags. Red, white, green from top to bottom is a different flag from green, white, red, so the order of the strips matters here.

A worked example

A state makes number plates with $2$ different letters, then $3$ digits. The digits may repeat. How many plates can it issue?

1. The first letter. Any of the $26$ letters: $26$ ways.
2. The second letter. It must differ from the first: $25$ ways.
3. The three digits. Each has $10$ ways, because digits may repeat.
4. Multiply. $26 \times 25 \times 10 \times 10 \times 10 = 650000$ plates.

The state could never list them all. The principle counts them in four lines.

Practise with new numbers

Try it in Python

The program lists every outfit with itertools.product, which takes one item from each list in every possible way. Then it counts the list, and compares with the product of the three sizes.

Common mistakes

• Adding instead of multiplying. $3$ shirts and $2$ pairs of trousers make $6$ outfits, not $5$. Each shirt goes with every pair.
• Keeping all the choices when repetition is not allowed. Without repetition, each place has one choice fewer than the place before.
• Forgetting a ban on a place. A number cannot start with $0$. A $3$-digit number has only $9$ choices for its first digit.
• Using the rule when the stages depend on each other. If the second count changes with the first choice, split the count into cases. The next lesson shows how.

Remember these

• Choices made one after another: multiply the numbers of ways.
• A tree diagram shows the rule. Every branch splits into the same number of branches.
• With repetition, each place keeps all its choices. Without repetition, each place has one choice fewer.
• Draw a box for each place, write its number of ways, and multiply.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. A café sells $4$ kinds of bread and $5$ fillings. A sandwich is one bread with one filling. How many sandwiches are possible?

2. How many $3$-letter codes can be made from the letters A to Z, if letters may repeat?

3. How many of those codes have three different letters?

4. A coin is tossed $3$ times. How many different sequences of heads and tails are there?

5. How many $2$-digit numbers are there? Count them with the principle, then check by subtraction.