A. Counting and Probability · Permutations and Combinations

Counting Strategies and the Multiplicative Counting Principle

A2.3 A2.1About 65 minutes

Learning goals

I can count outcomes by making a list, drawing a tree diagram or making a chart.
I can explain why these methods become impractical when there are many outcomes.
I can state and use the multiplicative (fundamental) counting principle for tasks done in stages.
I can handle restrictions by filling the most restricted position first.

Words to know

outcome
One possible result of an experiment or a choice, such as one particular outfit or one roll of two dice.

tree diagram
A branching diagram that shows every outcome of a task done in stages. Each path from the start to the end of a branch is one outcome.

multiplicative counting principle
If one task can be done in m ways and, after it, a second task can be done in n ways, then the two tasks together can be done in m × n ways. Also called the fundamental counting principle or the product rule.

stage
One step of a task that is done in steps, such as choosing the first digit of a code.

with repetition
The same item (for example the same digit) may be used more than once.

without repetition
Each item may be used at most once.

How many ways?

It is a cold January morning. You own 2 toques (a striped one and a plain one) and 3 scarves (wool, fleece and knit). How many different toque-and-scarf outfits can you wear to school?

You could just list them. But what if you also choose from 4 pairs of mittens, 3 jackets and 2 pairs of boots? Listing stops being practical very quickly. This unit is about counting without listing: finding how many ways something can happen, using a few powerful rules. Those counts are the key to many probability questions, from card games to lotteries to quality control in factories.

**Remember from the unit Probability: a sample space is the set of all possible outcomes, and when outcomes are equally likely, P(A) = n(A) ÷ n(S). Both n(A) and n(S) are counts**. This unit gives you the tools to find those counts when the sample space is far too large to list.

Three ways to organize outcomes

Make a list. Write the outcomes in a system so none are missed: striped + wool, striped + fleece, striped + knit, plain + wool, plain + fleece, plain + knit. That is 6 outfits.
Draw a tree diagram. Each stage is a set of branches. The first stage has 2 branches (toques). From each of those, the second stage has 3 branches (scarves). Count the ends of the branches.
Make a chart (table). For two stages, put one stage along the top and the other down the side. Each cell is one outcome.

All three methods give 6. They also show why the answer is 6: for each of the 2 toques there are 3 scarves, so there are 2 × 3 outcomes.

A tree diagram for the outfit problem. Each of the 2 first-stage branches splits into 3, so there are 2 × 3 = 6 paths, one for each outfit.

The multiplicative counting principle

If a task can be done in m ways, and after that a second task can be done in n ways, then the two tasks together can be done in m × n ways.

This works for any number of stages: multiply the number of choices at each stage. It is also called the fundamental counting principle.

The principle needs one condition: the number of choices at a stage must be the same no matter what was chosen earlier. (The actual choices may change. For example, if digits cannot repeat, the second digit has 9 choices whatever the first digit was, even though which 9 digits are left depends on the first.)

The key word is AND: a toque and a scarf; a first digit and a second digit and a third digit. When you hear "and then", think multiply.

A chart for rolling two dice. Each die has 6 outcomes, so the chart has 6 × 6 = 36 cells. The shaded cells are the 6 ways to roll a sum of 7.

Worked example

Example 1: Slots for an Ontario licence plate

Ontario passenger licence plates use four letters followed by three digits (for example ABCD 123). If every letter and every digit could be used, with repetition allowed, how many plates would be possible?

Draw 7 slots, one for each character: 4 letter slots and 3 digit slots.
Each letter slot has 26 choices (repetition is allowed). Each digit slot has 10 choices (0 to 9).
Apply the multiplicative counting principle: 26 × 26 × 26 × 26 × 10 × 10 × 10 = 26⁴ × 10³.
26⁴ = 456 976, so the total is 456 976 × 1000 = 456 976 000.

456 976 000 possible plates (in practice Ontario leaves some letters, such as I, O and Q, off its plates, so the real number is quite a bit smaller).

One box per character. Write the number of choices in each box, then multiply.

Worked example

Example 2: Without repetition

A bike lock has a 4-digit code (digits 0 to 9). How many codes are possible (a) if digits may repeat, (b) if no digit may repeat?

(a) Each of the 4 positions has 10 choices: 10 × 10 × 10 × 10 = 10 000.
(b) The first digit has 10 choices. Whatever it was, 9 digits are left for the second position, then 8, then 7.
10 × 9 × 8 × 7 = 5040.

(a) 10 000 codes; (b) 5040 codes. Notice the pattern 10 × 9 × 8 × 7: you will meet it again as a permutation in lesson 4.

Fill the most restricted position first

When some positions have extra rules ("the number must be even", "the first digit cannot be 0"), fill those slots first. Then count what is left for the other slots. If you fill an easy slot first, the number of choices for the restricted slot may depend on what you already chose, and the multiplication breaks down.

Worked example

Example 3: Restrictions

How many three-digit numbers (100 to 999) are odd and have three different digits?

Restrictions: the last digit must be odd (1, 3, 5, 7 or 9), and the first digit cannot be 0.
Last digit first: 5 choices.
First digit next: it cannot be 0 and cannot equal the last digit. From the 9 digits 1 to 9, remove the one used: 8 choices.
Middle digit: any digit except the two already used. 10 − 2 = 8 choices (0 is allowed here).
Multiply: 5 × 8 × 8 = 320.

320 numbers.

Worked example

Example 4: When the counts depend on earlier choices

A cafeteria meal is a main course and a drink. There are 4 mains. With the 3 hot mains you may choose from 5 drinks; with the cold sandwich you may choose from only the 2 cold drinks. How many meals are possible?

The number of drink choices depends on the main, so one multiplication will not work.
Split into cases. Hot main: 3 × 5 = 15 meals. Cold main: 1 × 2 = 2 meals.
The cases do not overlap, so add them: 15 + 2 = 17.

17 meals. Splitting into cases and adding is the additive counting principle, the topic of the next lesson.

Just for fun

Ontario leaves a few letters off its plates (for example I, O and Q, which are easy to mix up with digits), but the four-letter, three-digit pattern still allows hundreds of millions of plates, several times the number of people in Canada. So nobody should have to share.

Hands-on activity

Coin, die and tree

You need: one coin, one ordinary six-sided die, paper and a pencil.

Predict how many outcomes there are if you flip the coin and roll the die. Write your prediction.
Draw a tree diagram: 2 branches for the coin (H, T), then 6 branches from each for the die.
Now make a chart with H and T down the side and 1 to 6 across the top. Do the tree and the chart agree?
Flip and roll 30 times and tally which outcomes appear. Do they all show up eventually?
Extension: predict the number of outcomes for flipping the coin twice and rolling the die twice. Check with the counting principle.

What to look for: 2 × 6 = 12 outcomes (H1 to H6 and T1 to T6). In 30 trials most, but often not all, of the 12 will appear. The extension gives 2 × 2 × 6 × 6 = 144 outcomes, far too many to draw comfortably, which is exactly why the counting principle is useful.

Your turn

A pizza shop offers 3 crusts, 4 sauces and 6 toppings. A basic pizza has exactly one of each. How many basic pizzas are possible?

A coin is flipped 3 times. How many outcomes are in the sample space? List them.

Suppose a 7-digit phone number cannot start with 0 or 1. How many 7-digit numbers are possible?

Two dice are rolled. How many outcomes have a sum of 7? Use the chart in this lesson.

A password is 2 letters followed by 2 digits, with repetition allowed. How many passwords are possible?

How many three-digit numbers can be made from the digits 1, 2, 3, 4, 5 if no digit is repeated?

How many three-digit numbers (100 to 999) are even? Digits may repeat.

More practice: warm-up

You have 4 shirts and 3 pairs of pants. How many shirt-and-pants outfits are there?

A deli has 5 soups and 4 sandwiches. How many soup-and-sandwich lunches are possible?

A die is rolled twice. How many outcomes are there?

How many two-letter codes (such as QQ or AB) are possible if letters may repeat?

A quiz has 4 true-or-false questions. How many different answer sheets are possible?

More practice: on your own

How many 4-digit PINs have no repeated digit?

A plate has 3 letters followed by 3 digits. Letters may not repeat, but digits may. How many plates are possible?

How many odd three-digit numbers have all different digits? (Fill the restricted slots first.)

A multiple-choice test has 10 questions with 4 choices each. How many different ways can the test be answered if every question is answered?

A restaurant meal is a main course (5 choices), with an optional appetizer (3 choices) and an optional dessert (4 choices). How many different meals are possible?

Challenge

How many positive whole-number divisors does 720 have? (Hint: 720 = 2⁴ × 3² × 5.)

How many four-digit numbers (1000 to 9999) have at least one repeated digit?

How many even four-digit numbers have all different digits?

Check your understanding

Quiz

You own 3 toques and 4 scarves. How many toque-and-scarf outfits can you make?

Which situation is counted with the multiplicative counting principle?

How many 3-digit codes (000 to 999) are possible if digits may repeat?

A coin is flipped 5 times. How many outcomes are possible?

What is the main drawback of a tree diagram?

How many 4-digit PINs have no repeated digit?

For parents and teachers

Big idea (A2.3, A2.1): to count the outcomes of a task done in stages, multiply the number of choices at each stage. Lists, tree diagrams and charts show why this works, but they become impractical once the numbers grow; the counting principle and the permutation and combination formulas later in this unit are faster and less error-prone.

How to help: Use real choices at home: "We have 3 kinds of cereal, 2 kinds of milk and 2 fruits. How many breakfasts?" Ask your teen to draw the slots and write the choices in each.

Common difficulties:

Adding when they should multiply. "And then" means multiply.
Forgetting that 0 cannot be the first digit of a number (but can be in a code or PIN).
Filling an unrestricted slot first, so the count for a restricted slot changes from case to case. Encourage "restricted slots first".
Forgetting that "no repetition" reduces the choices by one at each stage.