1.2 - The product rule for counting

1.2 - The product rule for counting

Count thousands of possibilities without writing a single list. You will learn why counting multiplies, how to fill restricted positions first and how to split a count into cases, so that you can answer AQA's three-mark counting questions quickly and check them a second way.

Why counting multiplies

Counting questions ask how many ways something can be done, and the product rule answers them without writing out a list.

Here is a puzzle to keep in mind for the whole lesson. Exactly half of the 4-digit whole numbers are even: 4500 of the 9000. Now keep only the 4-digit numbers with no repeated digit, so 4071 stays but 4471 goes. Are there still equal numbers of odd and even ones? If not, which kind wins, and by how many? Listing them would take all day, because there are thousands. By the last part of this lesson you will settle it in four lines.

A small case first

A café meal deal is one drink and one snack. There are 3 drinks (tea, coffee, juice) and 4 snacks (apple, flapjack, crisps, yoghurt). The tree diagram shows every possible deal.

[DIAGRAM: asset_name: Tree of meal deals; asset_slug: l2fm-meal-deal-tree; caption: Every drink branches to every snack, giving 3 groups of 4 meal deals; description: Tree diagram from a start point to 3 drinks, tea, coffee and juice, each branching to the same 4 snacks, apple, flapjack, crisps and yoghurt. The 12 meal deals are numbered 1 to 12, braces mark 3 groups of 4 deals, and a box states 3 times 4 equals 12 meal deals]
Every drink branches to every snack, giving 3 groups of 4 meal deals

Each drink starts its own branch, and every one of the 4 snacks can follow it. So the deals come in 3 groups of 4, and there are 3×4=123 \times 4 = 12 of them. The number of snacks on offer is 4 whichever drink you chose. That is what makes the multiplication work.

Add a third stage, a choice of 2 cup sizes, and each of the 12 deals splits into 2. There are now 3×4×2=243 \times 4 \times 2 = 24 deals. Every new stage multiplies the count again.

Product rule for counting

If a task is done in stages, and each stage has the same number of choices whatever was chosen before it, then the number of ways to do the whole task is the product of the numbers of choices at the stages. For example, 3 drinks and then 4 snacks give 3×4=123 \times 4 = 12 meal deals. Not an example: choosing one item from 3 drinks or 4 snacks gives 3+4=73 + 4 = 7 choices, because only one choice is made.

“And then” or “or”

The wording tells you which operation to use. “A drink and then a snack” is one choice followed by another, so you multiply. “A drink or a snack” splits the outcomes into separate groups that cannot happen together, so you add the sizes of the groups. You will add in exactly this way in the last part, when a count splits into cases.

Key idea

Multiply the numbers of choices for stages that happen one after another; add the counts of separate cases that cannot happen together.

Counting when repeats are allowed

When an option can be used again, like a digit in a PIN, every position keeps its full set of choices, so you multiply the numbers of choices position by position.

You already know

There are ten digits, 0 to 9. A whole number never starts with 0, so the first digit of a 4-digit integer is 1 to 9. Odd numbers end in 1, 3, 5, 7 or 9; even numbers end in 0, 2, 4, 6 or 8; multiples of 5 end in 0 or 5.

Treat each position as a slot. Decide which digits or letters each slot may hold, write the number of choices in the slot, then multiply. A code or PIN may start with 0; an integer may not.

For example, a 4-digit PIN has 10 choices for every digit, so there are 10×10×10×10=10 00010 \times 10 \times 10 \times 10 = 10\,000 PINs, from 0000 to 9999. The 4-digit integers run from 1000 to 9999, and there are 9×10×10×10=90009 \times 10 \times 10 \times 10 = 9000 of them. The difference of 1000 is exactly the PINs that start with 0.

Repeated choices

If each of kk positions can be filled in nn ways, with repeats allowed, the number of arrangements is

n×n×⋯×n⏟k factors=nk\underbrace{n \times n \times \dots \times n}_{k \text{ factors}} = n^k

When the positions have different numbers of choices, multiply those numbers instead.
Not in the formula booklet: learn it.

Worked example 1: a locker code

Question. A locker code is two letters followed by three digits, for example KT507. Letters and digits may be repeated. Work out how many different codes there are.

Plan. Five slots: 26 choices for each letter and 10 for each digit. Multiply.

codes=26×26×10×10×10letters, then digits=676×1000262=676=676 000\begin{aligned} \text{codes} &= 26 \times 26 \times 10 \times 10 \times 10 && \text{letters, then digits} \\ &= 676 \times 1000 && 26^2 = 676 \\ &= 676\,000 \end{aligned}

Why this step? Every pair of letters can be followed by every one of the 1000 digit endings, 000 to 999, so the counts multiply.

Answer. There are 676 000676\,000 codes.

Check. Estimate: about 700×1000=700 000700 \times 1000 = 700\,000, which is close. ✓\checkmark

In Worked example 1 every slot had a simple rule. Exam questions usually give each position its own condition, and one of those conditions often includes the digit 0 without saying so.

Worked example 2: a different rule for each position

Question. A 4-digit integer has an odd first digit and a last digit less than 4. Digits may be repeated. Work out how many such integers there are.

Plan. List what each slot may hold, count it, then multiply.

first digit (odd):51,3,5,7,9second, third digits:10 eachno rulelast digit (<4):40,1,2,3total=5×10×10×4=2000\begin{aligned} \text{first digit (odd)} &: 5 && 1, 3, 5, 7, 9 \\ \text{second, third digits} &: 10 \text{ each} && \text{no rule} \\ \text{last digit} \ (< 4) &: 4 && 0, 1, 2, 3 \\ \text{total} &= 5 \times 10 \times 10 \times 4 = 2000 \end{aligned}

Why this step? “Less than 4” means 0, 1, 2 or 3. Zero is a digit, so it counts as a choice.

Answer. There are 2000 such integers.

Check. Of the 9000 four-digit integers, 59\frac59 have an odd first digit and 410\frac{4}{10} of the possible last digits are less than 4, so 9000×59×410=20009000 \times \frac59 \times \frac{4}{10} = 2000. ✓\checkmark

Here the rule “odd” already kept 0 out of the first slot. When a rule would allow 0 there, such as “an even first digit”, remove it yourself: an even first digit has only 4 choices, 2, 4, 6 or 8.

Watch out

Zero is a digit. For “a last digit less than 4”, the wrong line 5×10×10×3=15005 \times 10 \times 10 \times 3 = 1500 forgets 0. The correct line is 5×10×10×4=20005 \times 10 \times 10 \times 4 = 2000. AQA examiners report students who do not count zero.

The product you write is also what the examiner marks, so write it down before you work it out.

Exam tip

Write the product of choices, such as 5×10×10×45 \times 10 \times 10 \times 4, before evaluating it. AQA's schemes give marks for a product with most of its factors right even when the final answer is wrong; a wrong answer on its own scores nothing.

Counting when repeats are not allowed

When each item can be used only once, every choice removes one option from the next stage, so the numbers you multiply go down by one each time.

Three friends, Ada, Ben and Cal, sit in a row of three seats. The first seat can take any of the 3 friends, the second seat one of the 2 left, and the last seat whoever remains. That gives 3×2×1=63 \times 2 \times 1 = 6 orders, and you can list them to be sure: ABC, ACB, BAC, BCA, CAB, CBA. Who is left for the second seat depends on who sat first, but how many are left is always 2. The product rule only needs the number of choices to stay the same.

Factorial

For a positive integer nn, n!n! (read “nn factorial”) is the product of the whole numbers from nn down to 1: n!=n×(n−1)×⋯×2×1n! = n \times (n - 1) \times \dots \times 2 \times 1. For example, 4!=4×3×2×1=244! = 4 \times 3 \times 2 \times 1 = 24. Not an example: 5×4×35 \times 4 \times 3 is not 5!5!, because it stops after three factors.

Factorials grow astonishingly fast. Ernő Rubik built the first version of his cube in 1974, and the number of positions it can reach is 43 252 003 274 489 856 00043\,252\,003\,274\,489\,856\,000, about 4.3×10194.3 \times 10^{19}. That count comes from the product rule: 8!8! ways to place the corner pieces, 373^7 ways to twist them (the last corner's twist is then forced), 12!12! ways to place the edge pieces and 2112^{11} ways to flip them (the last edge's flip is forced), divided by 2 because only half of those arrangements can be reached by turning the faces.

Arranging different items

The number of ways to arrange nn different items in a row is n!n!.
The number of ways to fill rr positions in order from nn different items, with no repeats, is

n×(n−1)×(n−2)×⋯×(n−r+1)(r factors)n \times (n - 1) \times (n - 2) \times \dots \times (n - r + 1) \qquad (r \text{ factors})

Not in the formula booklet: learn it.

Worked example 1: arranging everything

Question. Six runners finish a race and there are no ties. Work out how many different finishing orders are possible.

Plan. Fill the places from 1st to 6th; each runner finishes only once.

orders=6×5×4×3×2×1one fewer runner each place=6!=720\begin{aligned} \text{orders} &= 6 \times 5 \times 4 \times 3 \times 2 \times 1 && \text{one fewer runner each place} \\ &= 6! \\ &= 720 \end{aligned}

Why this step? Whoever wins, 5 runners are left for second place, so second place always has 5 choices.

Answer. There are 720 finishing orders.

Check. Build up one runner at a time: 3 runners have 6 orders (like the three friends); a 4th runner can slot into any of 4 positions, giving 24; a 5th into any of 5, giving 120; a 6th into any of 6, giving 720. ✓\checkmark

Worked example 1 used every runner. Most exam questions use only some of the items, so the product stops early.

Worked example 2: filling only some of the places

Question. A 4-digit integer is made using four different digits chosen from 1, 2, 3, 4, 5, 6, 7. Work out how many different integers can be made.

Plan. Four slots: 7 digits for the first, then one fewer each time. Stop after four factors.

integers=7×6×5×44 slots, 4 factors=42×20pair the factors=840\begin{aligned} \text{integers} &= 7 \times 6 \times 5 \times 4 && \text{4 slots, 4 factors} \\ &= 42 \times 20 && \text{pair the factors} \\ &= 840 \end{aligned}

Why this step? None of the digits is 0, so the first slot can take any of the 7.

Answer. 840 different integers can be made.

Check. 7!3!=50406=840\dfrac{7!}{3!} = \dfrac{5040}{6} = 840: arrange all 7 digits, then ignore the order of the 3 that are not used. ✓\checkmark

On Paper 2 your calculator's x!x! key gives factorials quickly, but still write the product: it is the product that earns the method mark.

Watch out

“Different digits” means no repeats. The wrong line 7×7×7×7=24017 \times 7 \times 7 \times 7 = 2401 lets a digit be used again. The correct line is 7×6×5×4=8407 \times 6 \times 5 \times 4 = 840. AQA examiners single out this misreading in their reports.

Filling restricted positions first

When a condition controls one position, such as “odd” or “cannot start with 0”, fill that position first and then share out the digits that are left.

Try counting the odd 4-digit integers made from 1, 2, 3, 4, 5, 6 with no repeated digit by filling left to right. The first three slots take 6, then 5, then 4 choices. Now the units digit must be odd, but how many odd digits are left? If you used 1, 3 and 5 already, none; if you used 2, 4 and 6, all three. The number of choices depends on what came before, so the product rule cannot be used. Fill the units digit first and the problem disappears.

[DIAGRAM: asset_name: Fill the restricted position first; asset_slug: l2fm-fill-restricted-first; caption: Filling the units digit first makes every later count fixed; description: Two rows of four slots labelled thousands, hundreds, tens and units for odd 4-digit integers made from 1 to 6 with no repeated digit. Filling left to right gives 6, 5 and 4 and then a question mark in the units slot, because the number of odd digits left depends on earlier choices. Filling the units slot first gives 3 odd choices, then 5, 4 and 3 for the other slots, so 3 times 5 times 4 times 3 equals 180]
Filling the units digit first makes every later count fixed

Worked example 1: a condition on the last digit

Question. Work out how many odd 4-digit integers can be made from the digits 1, 2, 3, 4, 5, 6 with no digit repeated.

Plan. Fill the units digit first (it must be odd), then the other three slots from the 5 digits left.

units (odd):31,3 or 5thousands, hundreds, tens:5,4,3digits lefttotal=3×5×4×3=180\begin{aligned} \text{units (odd)} &: 3 && 1, 3 \text{ or } 5 \\ \text{thousands, hundreds, tens} &: 5, 4, 3 && \text{digits left} \\ \text{total} &= 3 \times 5 \times 4 \times 3 = 180 \end{aligned}

Why this step? Whichever odd digit goes in the units, exactly 5 digits remain, so the thousands always has 5 choices.

Answer. 180 odd integers can be made.

Check. Half of the six digits are odd, so half of all 6×5×4×3=3606 \times 5 \times 4 \times 3 = 360 arrangements should end in an odd digit: 360÷2=180360 \div 2 = 180. ✓\checkmark

Worked example 1 restricted the last digit. Now the restriction sits on the first digit, and it bans 0 there only, which changes the count for the second slot.

Worked example 2: zero among the digits

Question. Work out how many 4-digit integers can be made from the digits 0, 2, 4, 5, 7, 9 with no digit repeated.

Plan. The thousands digit cannot be 0, so fill it first. Then count what is left for each other slot, remembering that 0 is now allowed.

thousands:5any digit except 0hundreds:50 is allowed againtens, units:4,3digits lefttotal=5×5×4×3=300\begin{aligned} \text{thousands} &: 5 && \text{any digit except } 0 \\ \text{hundreds} &: 5 && 0 \text{ is allowed again} \\ \text{tens, units} &: 4, 3 && \text{digits left} \\ \text{total} &= 5 \times 5 \times 4 \times 3 = 300 \end{aligned}

Why this step? One non-zero digit has gone into the thousands, so 5 of the 6 digits remain for the hundreds, and 0 is one of them.

Answer. 300 integers can be made.

Check. Count everything and remove what is not allowed: 6×5×4×3=3606 \times 5 \times 4 \times 3 = 360 arrangements, of which 1×5×4×3=601 \times 5 \times 4 \times 3 = 60 start with 0, leaving 360−60=300360 - 60 = 300. ✓\checkmark

The digit 0 catches students in both directions: some let it lead, and others ban it from every slot.

Watch out

Zero is banned only from the first position. The wrong lines 6×5×4×3=3606 \times 5 \times 4 \times 3 = 360 (0 allowed to lead) and 5×4×3×2=1205 \times 4 \times 3 \times 2 = 120 (0 removed from every slot) both miss. The correct line is 5×5×4×3=3005 \times 5 \times 4 \times 3 = 300.

The check in Worked example 2 is a strategy in its own right, and it often turns an awkward count into an easy one.

Problem-solving

Count what you do not want. If a condition is awkward, count every arrangement, then subtract the ones that break the condition, as in 360−60=300360 - 60 = 300.

Splitting a count into cases

When two restricted positions compete for the same digits, the number of choices for one depends on what went into the other, so you split the count into cases, count each case with the product rule and add.

Take the even 3-digit integers made from 0, 1, 2, 3, 4 with no repeated digit. The units digit must be 0, 2 or 4, and the hundreds digit cannot be 0. Fill the units first, as usual. If the units digit is 0, the hundreds has 4 choices; if it is 2 or 4, the hundreds has only 3, because both 0 and the units digit are ruled out. One product cannot cover both, so count the two cases separately. They cannot happen together, so you add them, exactly as the “or” rule in the first part said.

Worked example 1: zero makes two cases

Question. Work out how many even 3-digit integers can be made from the digits 0, 1, 2, 3, 4 with no digit repeated.

Plan. Split on the units digit: 0 in one case, 2 or 4 in the other. In each case fill units, then hundreds, then tens.

units 0:4×3×1=12hundreds: 1, 2, 3, 4units 2 or 4:3×3×2=18hundreds: not 0, not unitstotal=12+18=30separate cases: add\begin{aligned} \text{units } 0 &: 4 \times 3 \times 1 = 12 && \text{hundreds: 1, 2, 3, 4} \\ \text{units } 2 \text{ or } 4 &: 3 \times 3 \times 2 = 18 && \text{hundreds: not 0, not units} \\ \text{total} &= 12 + 18 = 30 && \text{separate cases: add} \end{aligned}

Why this step? In the second case the tens can be 0 again, so it has 3 choices: 5 digits minus the 2 already used.

Answer. 30 even integers can be made.

Check. All 3-digit integers from these digits: 4×4×3=484 \times 4 \times 3 = 48. Odd ones end in 1 or 3: 3×3×2=183 \times 3 \times 2 = 18. Even ones: 48−18=3048 - 18 = 30. ✓\checkmark

In Worked example 1 the shared digit was 0. In the next example both ends of the number have conditions, and two digits appear in both lists. AQA has set this type as the final question of a paper.

Worked example 2: two conditions that overlap

Question. Five-digit integers are made using each of the digits 1, 3, 6, 7, 9 exactly once. Work out how many of these integers are greater than 60 00060\,000 and odd.

Plan. The first digit must be 6, 7 or 9; the last digit must be 1, 3, 7 or 9. The digits 7 and 9 are in both lists, so split by the first digit.

first 6:4×3!=24last: 1, 3, 7, 9first 7:3×3!=18last: 1, 3, 9first 9:3×3!=18last: 1, 3, 7total=24+18+18=60\begin{aligned} \text{first } 6 &: 4 \times 3! = 24 && \text{last: 1, 3, 7, 9} \\ \text{first } 7 &: 3 \times 3! = 18 && \text{last: 1, 3, 9} \\ \text{first } 9 &: 3 \times 3! = 18 && \text{last: 1, 3, 7} \\ \text{total} &= 24 + 18 + 18 = 60 \end{aligned}

Why this step? Once the first and last digits are fixed, the three middle digits can be arranged in 3!=63! = 6 ways.

Answer. 60 of the integers are greater than 60 00060\,000 and odd.

Check. Split by the last digit instead. Last digit 1 or 3: the first digit has 3 choices, giving 2×3×3!=362 \times 3 \times 3! = 36. Last digit 7 or 9: the first digit has 2 choices, giving 2×2×3!=242 \times 2 \times 3! = 24. Total 36+24=6036 + 24 = 60. ✓\checkmark

The tempting shortcut is to multiply the two lists together as if they were independent.

Watch out

The wrong line 3×4×3!=723 \times 4 \times 3! = 72 treats the first and last digits as independent. It counts impossible integers that start and end with 7, which would use the digit 7 twice. When the two lists share digits, split into cases: 24+18+18=6024 + 18 + 18 = 60.

Examiners mark these questions case by case, which rewards clear layout.

Exam tip

Label each case and its count, for example “first digit 6: 24”. AQA's three-mark schemes give two marks for correct case counts even when the final total is wrong. Do not list the integers: an incomplete list scores nothing.

Which method when

What the question givesWhat to do
Every position has a fixed number of choices whatever came beforeMultiply the slot counts
A condition on one positionFill that position first
Two conditions that share digits (often 0, or digits in both lists)Split into cases and add
A condition that is easier to break than to keepCount everything and subtract

Back to the opening puzzle

Now you can answer the question from the start of the lesson. Fill the units digit first. For even numbers, a units digit of 0 behaves differently from 2, 4, 6 or 8, because 0 is also the digit the thousands may not use. So the even count splits into two cases.

[DIAGRAM: asset_name: Even and odd cases; asset_slug: l2fm-even-odd-cases; caption: Splitting 4-digit integers with no repeated digit into even and odd cases; description: Three rows of four slots labelled thousands, hundreds, tens and units. Even with units digit 0 has 9, 8, 7 and 1 choices, giving 504. Even with units digit 2, 4, 6 or 8 has 8, 8, 7 and 4 choices, giving 1792, because the thousands digit cannot be 0 or the units digit. Odd has 8, 8, 7 and 5 choices, giving 2240. A box shows even 504 plus 1792 equals 2296, odd 2240, so 56 more even]
Splitting 4-digit integers with no repeated digit into even and odd cases

Exam-style example: more even numbers than odd

Question. Of the 4-digit integers with no repeated digit, are there more even ones or more odd ones? Work out how many more.

Plan. Fill the units digit first. Split the even integers into units digit 0 and units digit 2, 4, 6 or 8; count the odd ones in one go.

even, units 0=9×8×7×1=504even, units 2,4,6,8=8×8×7×4=1792odd=8×8×7×5=2240even−odd=504+1792−2240=56\begin{aligned} \text{even, units } 0 &= 9 \times 8 \times 7 \times 1 = 504 \\ \text{even, units } 2, 4, 6, 8 &= 8 \times 8 \times 7 \times 4 = 1792 \\ \text{odd} &= 8 \times 8 \times 7 \times 5 = 2240 \\ \text{even} - \text{odd} &= 504 + 1792 - 2240 = 56 \end{aligned}

Why this step? A units digit of 0 uses up the very digit the thousands could not take anyway, so the thousands still has 9 choices. Every other units digit leaves 0 in play, so the thousands loses two options, 0 and the units digit, and has 8.

Answer. There are 56 more even integers than odd ones: 2296 even and 2240 odd.

Check. 2296+2240=45362296 + 2240 = 4536, and the total number of 4-digit integers with no repeated digit is 9×9×8×7=45369 \times 9 \times 8 \times 7 = 4536. ✓\checkmark

Your turn: the question below works like Worked example 2, but now the first digit must be small rather than large.

Quick Recap

  • Multiply the numbers of choices for stages that happen one after another; add the counts of separate cases.
  • With repeats allowed, each position keeps its full set of choices. Zero is a digit, but an integer cannot start with it.
  • Without repeats, each choice removes one option: n!n! arranges nn different items, and 7×6×5×47 \times 6 \times 5 \times 4 fills 4 places from 7 digits.
  • Fill restricted positions first. If two restrictions share digits, split into cases and add; if a condition is awkward, count everything and subtract.

The opening puzzle: there are 56 more even than odd 4-digit integers with no repeated digit, because a units digit of 0 never blocks the thousands digit.