Counting Techniques

Lessons

Senior 6 · Basic Mathematics

Counting Techniques

5 lessons

Lesson 2 of 5

The sum principle and the product rule

25 min

Too many to list

A mobile-money PIN of four digits can be anything from 0000 to 9999. Listing them all would take hours, yet everyone knows there are 10 000 of them. That number comes from a rule, not a list. The canteen tree diagram of the last lesson already showed the idea: 2 starch choices, each followed by 3 sauces, gave $2 \times 3 = 6$ plates. This lesson states the two basic rules of counting.

Definition

The sum principle (addition rule). If one choice can be made in $m$ ways and another in $n$ ways, and the two choices are mutually exclusive (no way belongs to both), then choosing one or the other can be done in $m + n$ ways.

Example: a student must read one novel, chosen from 5 English novels or 4 Kiswahili novels: $5 + 4 = 9$ ways.

Definition

The product rule (multiplication principle). If a task is done in stages, with $m$ ways for the first stage and, for each of these, $n$ ways for the second, then the whole task can be done in $m \times n$ ways. For $k$ stages: $m_1 \times m_2 \times \cdots \times m_k$ .

Example: a shirt from 4 and a pair of trousers from 3 gives $4 \times 3 = 12$ outfits.

"Or" adds, "and then" multiplies

The sum principle is for alternatives: you do one thing or another. The product rule is for stages: you do one thing and then another. The reason for the product rule is the tree diagram: each of the $m$ first branches carries the same $n$ second branches, so there are $n + n + \cdots + n = m \times n$ paths.

Ordered samples

Choosing $r$ items one after another from $n$ , where order matters, is an ordered sample.

With replacement (an item may be chosen again): each stage has $n$ choices, so there are $n^{r}$ ordered samples.
Without replacement (each item at most once): the choices fall by one each time, giving $n(n-1)(n-2)\cdots(n-r+1)$ .

Worked example

Worked example 1: PINs. How many 4-digit PINs are there (a) if digits may repeat; (b) if no digit repeats; (c) if no digit repeats and the PIN does not begin with 0?

(a) Four stages of 10 choices: $10^4 = 10\,000$ .

(b) $10 \times 9 \times 8 \times 7 = 5040$ .

(c) First digit: 9 choices (1 to 9). Second: 9 (any digit except the first, now including 0). Third: 8. Fourth: 7. Total $9 \times 9 \times 8 \times 7 = 4536$ .

Deal with the restricted position first; that is why (c) starts with the first digit.

Worked example

Worked example 2: sum and product together. Using the digits 1, 2, 3, 4, 5 without repetition, how many numbers less than 1000 can be made?

A number less than 1000 has 1, 2 or 3 digits. These cases are mutually exclusive, so count each with the product rule and add:

\underbrace{5}_{\text{1 digit}} + \underbrace{5 \times 4}_{\text{2 digits}} + \underbrace{5 \times 4 \times 3}_{\text{3 digits}} = 5 + 20 + 60 = 85

Worked example

Worked example 3: a condition on the last digit. How many three-digit even numbers can be made from 1, 2, 3, 4, 5 without repetition?

The last digit must be 2 or 4: 2 choices. Then the first digit has 4 choices left and the middle digit 3. Total: $2 \times 4 \times 3 = 24$ .

Worked example

Worked example 4: number plates. Suppose plates have the illustrative form three letters, three digits, one letter, for example ABC 123 D, with repetition allowed. How many plates are possible?

26 \times 26 \times 26 \times 10 \times 10 \times 10 \times 26 = 26^4 \times 10^3 = 456\,976\,000

Khan Academy India: when to add and when to multiply. Listen for the words 'and' and 'or' in each problem and match them to the product rule and the sum principle.

Warning

Adding when you should multiply. "A shirt and trousers" is two stages: multiply. "A novel in English or in Kiswahili" is one choice from two separate groups: add. And use the sum principle only when the groups do not overlap; if they do, subtract the overlap (inclusion–exclusion).

Tip

Draw a box for each stage, write the number of choices in each box, then multiply. Fill the boxes with restrictions first.

✦

Practice

A menu has 3 starters, 5 main dishes and 2 desserts. How many three-course meals are possible?
A traveller can go from town A to town B by one of 4 buses or one of 2 trains. In how many ways can she travel?
How many 3-letter "words" can be made from the 26 letters (a) with repetition; (b) without repetition?
How many odd three-digit numbers can be formed from 1, 2, 3, 4, 5, 6 without repetition?
How many numbers between 100 and 999 (inclusive) have all digits different?
A quiz has 10 true/false questions. In how many ways can all of them be answered?
How many numbers greater than 3000 can be formed from the digits 1, 2, 3, 4 without repetition? Explain.

Show answersHide answers

$3 \times 5 \times 2 = 30$ .
$4 + 2 = 6$ (one journey, by bus or by train).
(a) $26^3 = 17\,576$ . (b) $26 \times 25 \times 24 = 15\,600$ .
Last digit 1, 3 or 5: 3 ways; then $5 \times 4$ . Total $3 \times 5 \times 4 = 60$ .
First digit 9 ways (not 0), second 9, third 8: $648$ .
$2^{10} = 1024$ .
Only 4-digit numbers can exceed 3000. The first digit must be 3 or 4: 2 ways; then $3 \times 2 \times 1$ . Total $2 \times 6 = 12$ .

Important

Alternatives that cannot both happen: add. Stages done one after another: multiply. Ordered samples: $n^{r}$ with replacement, $n(n-1)\cdots(n-r+1)$ without.

Sources and credits

Text, diagram, worked examples and exercises: Written by Ganzaa. The number-plate format is illustrative.

Video: Using AND and OR | Permutations and Combinations, Khan Academy India - English, embedded from YouTube.

1Too many to list

2"Or" adds, "and then" multiplies

3Ordered samples

Too many to list

"Or" adds, "and then" multiplies

Ordered samples