Counting rules

How many different outfits can you make from 4 shirts, 3 pairs of trousers and 2 pairs of shoes? You could list them all, but the list would be long and easy to get wrong. Counting rules let you find the number by thinking about the structure of the choice instead of writing everything down. They are the foundation for permutations, combinations and probability.

The addition rule

Suppose you want to read one book from the shelf. There are 5 maths books and 4 novels. You pick either a maths book or a novel, never both at once, so there are $5+4=9$ possible choices.

The key words are "or" and "mutually exclusive": a single choice belongs to exactly one group.

The multiplication rule

Now suppose you want to pick a snack and a drink. The choice happens in successive steps. A tree diagram shows every possibility: from the start you choose a drink (tea or juice), and for each drink you choose a snack (cake, fruit or nuts).

Count the right-hand ends of the tree: $3+3=6$, which is the same as $2\times 3$.

The key word is "and": you do step 1 and then step 2 and then step 3.

Numbers, passwords and routes

Numbers with restrictions

When a digit has a restriction, fill the most restricted position first.

Passwords

Routes

The complement trick

Sometimes it is easier to count what you do not want. If $N$ is the total number of possibilities and $M$ of them do not satisfy the condition, then the number that do satisfy it is $N-M$.

Checking by computer

A short program can check a counting argument by brute force. Here it tests the first example above:

count = 0
for n in range(100, 1000):
    if len(set(str(n))) == 3:
        count += 1
print(count)   # 648

Key terms

Summary

• Addition rule: choices that cannot happen together, add the numbers ("or").
• Multiplication rule: successive steps, multiply the numbers ("and then").
• A tree diagram lists all outcomes and shows why the product works.
• For numbers with restrictions, fill the most restricted position first and split into cases when needed.
• Complement trick: (all) $-$ (the ones you do not want).

Practice

Show solutions

1. Three successive steps: $3\cdot 5\cdot 2=30$ meals.
2. (a) One book from either group, groups do not overlap: $6+4=10$. (b) One of each, two steps: $6\cdot 4=24$.
3. Each of the 3 digits is chosen from $\{1,3,5,7,9\}$: $5\cdot 5\cdot 5=125$.
4. $26\cdot 26\cdot 10\cdot 10\cdot 10=676\,000$.
5. A number divisible by 5 ends in 0 or 5. Units digit 0: hundreds 9 ways, tens 8 ways, $72$ numbers. Units digit 5: hundreds digit not 0 and not 5, so 8 ways; tens digit 8 ways; $64$ numbers. Total $72+64=136$.
6. One way from A to C: $3\cdot 4+2=14$ routes. The way back is also one of these 14 routes, chosen independently, so $14\cdot 14=196$ round trips.
7. (a) $2^8=256$. (b) Complement: only the string of all 0s has no 1, so $256-1=255$. (c) First and last symbols are fixed, the 6 middle ones are free: $2^6=64$.
8. Total 9000. With no digit 0: $9^4=6561$. So $9000-6561=2439$.
9. $360=2^3\cdot 3^2\cdot 5$. A divisor is $2^a3^b5^c$ with $a\in\{0,1,2,3\}$, $b\in\{0,1,2\}$, $c\in\{0,1\}$: $4\cdot 3\cdot 2=24$ divisors.
10. The first stripe has 5 colours; each next stripe has 4 colours (anything but the colour next to it): $5\cdot 4\cdot 4=80$.