The Product Rule for Counting – OCR FSMQ Additional Maths

1 The Product Rule

EN3 — the product rule for counting

If a task has $m$ ways of doing stage 1 and $n$ ways of doing stage 2,
there are $m \times n$ ways of doing both

The word to watch for is "and". Stages joined by "and" multiply. Separate, mutually exclusive cases joined by "or" add.

Worked Example 1 — Several stages

A password is made of one letter (26 choices), then two digits, then one symbol from a set of $8$. How many passwords are possible?

①Four independent stages: $26$, $10$, $10$, $8$.

②$26 \times 10 \times 10 \times 8 = 20\,800$

Worked Example 2 — The specification's examples

The specification names two cases directly.

①Rolling $n$ dice: each die has $6$ outcomes, independently, so there are $6^n$ outcomes.

②For $3$ dice: $6^3 = 216$.

③Arranging $n$ distinct objects: $n$ choices for the first place, $n-1$ for the second, and so on.

④$n \times (n-1) \times \cdots \times 1 = n!$

These two look similar but differ crucially: dice can repeat a value, so the count stays at $6$ each time. Objects being arranged are used up, so the count drops by one each time.

2 With or Without Repetition

The two patterns

Repetition allowed: $n \times n \times n \times \cdots = n^k$ (for $k$ stages)
No repetition: $n \times (n-1) \times (n-2) \times \cdots$

Worked Example 3 — Both versions of the same question

How many three-digit codes can be made from the digits $1$ to $5$ (a) if digits may repeat, (b) if they may not?

①(a) Five choices at each of three stages: $5 \times 5 \times 5 = 125$

②(b) Each digit used up: $5 \times 4 \times 3 = 60$

③Note that (b) is ${}^5P_3$ — a permutation.

Read the question for the word "different". "Three different digits" means no repetition; without that word, repetition is usually allowed.

3 Arrangements and Factorials

Factorial notation

$n! = n \times (n-1) \times \cdots \times 2 \times 1$, and by convention $0! = 1$

$n$	$n!$
$0$	$1$
$1$	$1$
$2$	$2$
$3$	$6$
$4$	$24$
$5$	$120$
$6$	$720$
$10$	$3\,628\,800$

Factorials grow terrifyingly fast. $20!$ is already about $2.4 \times 10^{18}$. If a question's answer is a modest number, you probably need a combination, not a factorial.

Worked Example 4 — Objects that must stay together

Six people sit in a row. In how many ways can they be arranged if two particular people must sit next to each other?

①Treat the pair as a single block. Then there are $5$ items to arrange: the block and the other four people.

②$5! = 120$ ways to arrange those five items.

③Within the block, the two people can swap: $2! = 2$ ways.

④By the product rule: $120 \times 2 = 240$

The "block" trick is standard whenever items must be adjacent: glue them together, arrange, then multiply by the internal arrangements.

Worked Example 5 — A restriction on one position

How many four-digit numbers can be formed from the digits $1, 2, 3, 4, 5$ without repetition, if the number must be even?

①Deal with the restriction first. The last digit must be $2$ or $4$: $2$ choices.

②That digit is now used, leaving $4$ digits for the first position, $3$ for the second, $2$ for the third.

③$2 \times 4 \times 3 \times 2 = 48$

Always handle the restricted position first. If you fill the free positions first, you will not know how many choices remain for the restricted one.

4 When to Add Instead

Add when the possibilities fall into separate cases that cannot both happen. Multiply when you are making a sequence of choices that all happen.

Worked Example 6 — Adding cases

A code is either two letters ($26$ each) or three digits. How many codes are possible?

①Two letters: $26 \times 26 = 676$

②Three digits: $10 \times 10 \times 10 = 1000$

③These are alternatives, so add: $676 + 1000 = 1676$

Within each case you multiply; between the cases you add. Most harder counting questions need both operations.

Worked Example 7 — Counting the complement

How many three-digit numbers (from $100$ to $999$) contain at least one zero?

①"At least one" is awkward directly, so count the opposite: numbers with no zero.

②Total three-digit numbers: first digit $1$–$9$ ($9$ ways), other two $0$–$9$: $9 \times 10 \times 10 = 900$

③No zero anywhere: each digit from $1$–$9$: $9 \times 9 \times 9 = 729$

④At least one zero: $900 - 729 = 171$

The complement is almost always faster for "at least one" questions — in counting and in probability alike.

5 Quick Reference

"And"

Multiply.

"Or"

Add (if the cases cannot overlap).

Repetition allowed

$n^k$ for $k$ stages.

No repetition

$n(n-1)(n-2)\cdots$

All $n$ arranged

$n!$

$0!$

Equals $1$.

Must be together

Treat as a block, then $\times\,$ internal arrangements.

Restrictions

Fill the restricted position first.

"At least one"

Total minus none.

Sanity check

Does the size of the answer feel plausible?

6 Practice Questions

Question 1

A shop sells $5$ styles of shirt in $7$ colours. How many different shirts are stocked?

▶ Show solution

$5 \times 7 = 35$

Question 2

Four dice are rolled. How many possible outcomes are there?

▶ Show solution

$6^4 = 1296$

Question 3

In how many orders can $8$ runners finish a race?

▶ Show solution

$8! = 40\,320$

Question 4

How many four-letter arrangements can be made from the letters of MATHS, with no letter repeated?

▶ Show solution

$5$ letters available, choosing $4$ in order:

$5 \times 4 \times 3 \times 2 = 120$

Question 5

A car registration is $2$ letters, then $2$ digits, then $3$ letters. How many are possible if repeats are allowed?

▶ Show solution

$26^2 \times 10^2 \times 26^3$

$= 676 \times 100 \times 17\,576 = 1\,188\,137\,600$

Question 6

Five people sit in a row, but two of them refuse to sit next to each other. How many arrangements are possible?

▶ Show solution

Total arrangements: $5! = 120$.

Arrangements with them together: block of $2$ plus $3$ others gives $4! = 24$, times $2$ for the swap $= 48$.

$120 - 48 = 72$

Question 7

How many three-digit numbers can be made from $1, 2, 3, 4, 5, 6$ without repetition if the number must be greater than $500$?

▶ Show solution

The first digit must be $5$ or $6$: $2$ choices.

Then $5$ remaining digits for the second place and $4$ for the third.

$2 \times 5 \times 4 = 40$

Question 8

A lock uses either a $4$-digit code or a $3$-letter code. How many combinations must a thief try in the worst case?

▶ Show solution

Digits: $10^4 = 10\,000$

Letters: $26^3 = 17\,576$

These are alternatives, so add: $27\,576$.

Question 9

Six books — three maths and three physics — are arranged on a shelf. How many arrangements keep all the maths books together?

▶ Show solution

Treat the three maths books as one block. That leaves $4$ items (block + $3$ physics books).

$4! = 24$ arrangements of the items.

Within the block, $3! = 6$ orders.

$24 \times 6 = 144$

Question 10

A $5$-character ID is made from the $26$ capital letters and the $10$ digits.

(a) How many IDs are possible if characters may repeat? (b) How many if all five characters must be different? (c) How many contain at least one digit? (d) The designers want at least $50$ million IDs while keeping all characters different. Is a $5$-character ID enough?

▶ Show solution

There are $26 + 10 = 36$ available characters.

(a) $36^5 = 60\,466\,176$

(b) $36 \times 35 \times 34 \times 33 \times 32$

$= 45\,239\,040$

(c) Count the complement: IDs made of letters only.

$26^5 = 11\,881\,376$

At least one digit $= 60\,466\,176 - 11\,881\,376 = 48\,584\,800$

(d) From (b), the number of all-different $5$-character IDs is $45\,239\,040$, which is less than $50$ million.

So no — a $5$-character ID is not enough under that restriction. Note that (a) shows allowing repeats would be sufficient ($60.5$ million), so the designers must either permit repeated characters or extend the ID to $6$ characters. Adding a sixth character while keeping all different gives $45\,239\,040 \times 31 \approx 1.4$ billion, comfortably enough.

The Product Rule for Counting (EN3) · OCR FSMQ Additional Maths · Created with MathJax