Combinatorics

Lessons

Senior 4 · Mathematics

Combinatorics

5 lessons

Lesson 2 of 5

The multiplication principle and arrangements

25 min

How safe is a padlock code?

A combination padlock with 3 wheels, each showing the digits 0 to 9, has $10 \times 10 \times 10 = 1000$ possible codes; one with 4 wheels has $10\,000$ . Someone who tries one code every 3 seconds needs up to 50 minutes to open the first lock, but more than 8 hours for the second. One extra wheel multiplies the work by 10. That multiplication is the most useful counting rule there is.

Definition

Multiplication principle: if a task is done in $k$ successive stages, and the stages can be done in $n_1, n_2, \dots, n_k$ ways, where the number of ways at each stage does not depend on the choices made before, then the whole task can be done in

n_1 \times n_2 \times \dots \times n_k \text{ ways}.

Addition principle: if a task can be done in one of several separate ways (no overlap), with $m_1, m_2, \dots$ possibilities, the total is $m_1 + m_2 + \dots$ .

Example: a lunch of 1 of 3 starches and 1 of 2 sauces: $3 \times 2 = 6$ meals. A drink that is either 1 of 4 juices or 1 of 3 teas: $4 + 3 = 7$ choices.

Tip

"And then" means multiply; "or" (with no overlap) means add. Before you calculate, say the task aloud in stages: "choose the first digit, and then the second, and then…".

Definition

Factorial: for a natural number $n \ge 1$ , $n! = n \times (n - 1) \times \dots \times 2 \times 1$ , read " $n$ factorial". By definition $0! = 1$ .

Why $0! = 1$ : the rule $n! = n \times (n - 1)!$ with $n = 1$ gives $1! = 1 \times 0!$ , so $0!$ must be 1 for the rule to hold.

Examples: $5! = 120$ , $\frac{10!}{8!} = 10 \times 9 = 90$ , $7! = 7 \times 6! = 5040$ .

Arrangements with repetition

An arrangement is an ordered list. Each wheel of the padlock can show any of the 10 digits, whatever the other wheels show: the digits may repeat. Filling $p$ ordered places from $n$ symbols, with repetition allowed, gives $n$ choices for every place.

Important

Arrangements with repetition. The number of ordered lists of length $p$ whose entries are chosen from $n$ objects, repetition allowed, is

n^{p} .

Reason: $p$ stages, each with $n$ choices, so $n \times n \times \dots \times n = n^p$ by the multiplication principle.

Worked example 1: codes and answer sheets

(a) A phone network gives numbers of the form 078 followed by any 7 digits. How many numbers are possible? (b) In how many ways can a 10-question true/false test be answered? (c) How many 3-letter "words" (any strings) can be made from the 26 letters of the alphabet?

Solution

The 7 free places each take 10 digits: $10^7 = 10\,000\,000$ numbers.
Each question has 2 answers: $2^{10} = 1024$ answer sheets. So a pupil who guesses has only a 1 in 1024 chance of a perfect score.
$26^3 = 17\,576$ .

Arrangements without repetition

When an object, once used, cannot be used again, the number of choices goes down by one at each stage. Choosing a president, then a secretary, then a treasurer from the 12 members of a club gives $12 \times 11 \times 10 = 1320$ ways: whoever is president cannot also be secretary.

Important

Arrangements without repetition. The number of ordered lists of $p$ different objects chosen from $n$ objects ( $0 \le p \le n$ ) is

A_n^p = n(n - 1)(n - 2)\cdots(n - p + 1) = \frac{n!}{(n - p)!} .

Reason: $n$ choices for the first place, $n - 1$ for the second, …, $n - p + 1$ for the $p$ th. Multiplying and dividing by $(n - p)!$ gives the factorial form.

Notation: also written ${}^nP_r$ or $P (n, p)$ ; calculators have an $n P r$ key. For example $A_{12}^3 = \frac{12!}{9!} = 1320$ .

Worked example 2: four-digit numbers

Using only the digits 1, 2, 3, 4, 5, 6, 7, how many four-digit numbers can be formed (a) if digits may repeat, (b) if no digit repeats, (c) if no digit repeats and the number is even?

Solution

With repetition: $7^{4} = 2401$ .
Without repetition: $A_7^4 = 7 \times 6 \times 5 \times 4 = 840$ .
The units digit is restricted, so fill it first: it must be 2, 4 or 6 (3 choices). The other three places are then filled from the 6 remaining digits: $6 \times 5 \times 4$ .

So there are $3 \times 6 \times 5 \times 4 = 360$ even numbers.

Worked example 3: conditions and the addition principle

A club has 12 members, among them Uwase. (a) In how many ways can a president, a secretary and a treasurer be chosen if Uwase must be the president? (b) If Uwase must hold one of the three posts? (c) How many numbers of one, two or three digits can be made from the digits 1 to 5 with no digit repeated?

Solution

President fixed (1 way), then secretary and treasurer from the other 11: $11 \times 10 = 110$ .
Choose Uwase's post (3 ways), then fill the other two posts from 11 people: $3 \times 11 \times 10 = 330$ .
The three lengths are separate cases, so add: $A_{5}^{1} + A_{5}^{2} + A_{5}^{3} = 5 + 20 + 60 = 85$ .

Warning

Fill the restricted places first. If you fill the thousands, hundreds and tens first, the number of even digits left for the units depends on what you already used, and the multiplication principle no longer applies directly. Also watch for 0: a number cannot start with 0, so "four-digit numbers from the digits 0 to 9 without repetition" is $9 \times 9 \times 8 \times 7 = 4536$ , not $A_{10}^4 = 5040$ .

The Organic Chemistry Tutor: The Fundamental Counting Principle. Watch the box method for license plates and codes, with and without repetition.

✦

Practice

Try each one before opening the answers. They get harder as you go.

Evaluate (a) $6!$ (b) $\frac{9!}{7!}$ (c) $A_{8}^{3}$ (d) $\frac{0!}{1!}$ .
A shop sells shirts in 5 colours and 4 sizes. How many different shirts (colour and size) can it stock?
How many 5-digit PIN codes are possible if every digit 0–9 may be used and may repeat? How many if no digit repeats?
In how many ways can 8 runners finish first, second and third in a race (no ties)?
How many three-digit numbers can be formed from the digits 0, 1, 2, 3, 4, 5 (a) with repetition allowed, (b) without repetition?
How many numbers between 3000 and 6000 can be formed from the digits 1, 3, 5, 6, 8 if no digit repeats?
Solve for $n$ : $A_{n}^{2} = 72$ .

Show answersHide answers

(a) 720 (b) $9 \times 8 = 72$ (c) $8 \times 7 \times 6 = 336$ (d) 1.
$5 \times 4 = 20$ .
With repetition $10^5 = 100\,000$ ; without, $A_{10}^5 = 10 \times 9 \times 8 \times 7 \times 6 = 30\,240$ .
$A_8^3 = 8 \times 7 \times 6 = 336$ .
(a) First digit 1–5 (5 ways), others 6 ways each: $5 \times 6 \times 6 = 180$ . (b) $5 \times 5 \times 4 = 100$ (the second place may use 0 but not the first digit).
The first digit must be 3 or 5 (2 ways); then $4 \times 3 \times 2$ for the rest: $2 \times 24 = 48$ .
$n (n - 1) = 72$ , so $n^{2} - n - 72 = 0$ , $(n - 9) (n + 8) = 0$ , and $n = 9$ ( $n$ must be a natural number).

Quick check

A motorbike taxi app lets a rider choose 1 of 4 pick-up points and then 1 of 6 drop-off points. How many different trips are possible?

Key points

Stages done one after another: multiply; separate cases: add.
$n! = n(n - 1)\cdots 1$ , with $0! = 1$ .
Ordered lists of length $p$ from $n$ objects: $n^{p}$ with repetition, $A_n^p = \frac{n!}{(n - p)!}$ without.
Fill restricted places first, and remember that a number cannot begin with 0.

Sources and credits

Written by Ganzaa: the explanations, the diagram, the worked examples, the practice items and the questions.
Photo: Three padlocks, Mx. Granger, Wikimedia Commons, CC0 1.0.
Video: The Fundamental Counting Principle, The Organic Chemistry Tutor, embedded from YouTube.

1How safe is a padlock code?

2Arrangements with repetition

3Arrangements without repetition

How safe is a padlock code?

Arrangements with repetition

Arrangements without repetition