Counting Principles

To find a probability, you often need to know how many outcomes there are. Listing them works for small problems, but nobody wants to list every possible licence plate. Two simple rules, the additive and multiplicative counting principles, let you count huge sets of outcomes without writing them all down.

Key ideas

Lists and tree diagrams

For small problems, list the outcomes in an organized way, or draw a tree diagram with one level of branches for each stage. For example, with $3$ shirts (red, blue, green) and $2$ pairs of pants (jeans, khakis), a tree has $3$ first branches, each splitting into $2$:

Shirt	Pants	Outfit
red	jeans, khakis	$2$ outfits
blue	jeans, khakis	$2$ outfits
green	jeans, khakis	$2$ outfits

That’s $3 \times 2 = 6$ outfits. Lists and trees are great for checking your thinking, but they get too big very quickly. The counting principles do the same job with arithmetic.

The multiplicative counting principle

If a task is done in stages, with $m$ ways to do the first stage and $n$ ways to do the second, then there are

$$m \times n$$

ways to do the whole task. This extends to any number of stages: multiply the number of choices at each stage. The key word is “and”: you choose a shirt and pants.

The additive counting principle

If a choice can be made in one of two ways that don’t overlap, with $m$ options of the first kind or $n$ options of the second kind, then there are

$$m + n$$

options altogether. The key word is “or”: you pick a hot meal or a sandwich, not both. (If the two kinds can overlap, subtract the overlap, just like the additive principle for probability.)

Factorial notation

The product of all the whole numbers from $n$ down to $1$ is written $n!$ and read ”$n$ factorial”:

$$n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$$

For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. By the multiplicative principle, $n!$ is the number of ways to arrange $n$ different objects in a row: $n$ choices for the first spot, $n - 1$ for the next, and so on.

We also define

$$0! = 1$$

It may look strange, but there is exactly one way to arrange nothing (do nothing!), and this choice makes the formulas on the next pages work. Most calculators have an $n!$ or $x!$ key.

Factorials grow very fast, so cancel before you multiply:

$$\frac{8!}{6!} = \frac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56$$

Worked examples

Example 1: Outfits

You have $3$ shirts, $2$ pairs of pants, and $2$ pairs of shoes. How many different outfits can you make?

Solution. Choosing an outfit has three stages: shirt and pants and shoes. By the multiplicative principle:

$$3 \times 2 \times 2 = 12 \text{ outfits}$$

Check: the tree diagram above had $6$ shirt-and-pants branches, and each now splits into $2$ shoe branches, giving $12$. ✓

Example 2: Using both principles

A cafeteria offers $4$ hot meals and $3$ sandwiches. You pick one main dish, plus one of $5$ drinks. How many different lunches are possible?

Solution. The main dish is a hot meal or a sandwich, which don’t overlap, so add: $4 + 3 = 7$ main dishes. Then you choose a main dish and a drink, so multiply:

$$7 \times 5 = 35 \text{ lunches}$$

Example 3: Codes with and without repetition

• (a) A licence plate has $4$ letters followed by $3$ digits. How many plates are possible if letters and digits can repeat?
• (b) How many three-digit numbers (from $100$ to $999$) have no repeated digits?

Solution. (a) There are $26$ choices for each letter and $10$ for each digit:

$$26 \times 26 \times 26 \times 26 \times 10 \times 10 \times 10 = 456\,976\,000$$

(b) Fill the most restricted spot first. The first digit can’t be $0$, so it has $9$ choices. The second digit can be anything except the first: $9$ choices (now $0$ is allowed). The third can be anything except the first two: $8$ choices.

$$9 \times 9 \times 8 = 648$$

Example 4: Factorials

Six friends line up for a photo. How many different orders are possible? Then simplify $\dfrac{10!}{8!}$.

Solution. There are $6$ choices for the first spot, $5$ for the second, and so on:

$$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$$

For the fraction, write $10!$ as $10 \times 9 \times 8!$ and cancel:

$$\frac{10!}{8!} = \frac{10 \times 9 \times 8!}{8!} = 90$$

Common mistakes

Adding when you should multiply. If you choose one thing and then another, multiply. Only add when the options are separate alternatives (one or the other).

Forgetting that choices shrink without repetition. If a digit or person can’t be used twice, each stage has one fewer option than the stage before.

Ignoring restrictions until the end. Deal with the most restricted position first (like “the first digit can’t be $0$”), then fill in the rest.

Thinking $0! = 0$. By definition, $0! = 1$.

Multiplying out huge factorials. Cancel first: $\dfrac{100!}{98!} = 100 \times 99 = 9900$. Your calculator may overflow on $100!$, but you don’t need it.

Practice

1. (Warm-up) An ice cream shop has $4$ flavours, $3$ toppings, and a choice of cone or cup. How many different single-scoop orders (one flavour, one topping, cone or cup) are possible?

Solution

$$4 \times 3 \times 2 = 24$$

2. (Warm-up) Evaluate $6!$, $\dfrac{9!}{7!}$, and $0!$.

Solution

$6! = 720$, $\dfrac{9!}{7!} = 9 \times 8 = 72$, and $0! = 1$.

3. (Warm-up) You want to borrow one book: either one of $5$ mystery novels or one of $7$ science-fiction novels. How many choices do you have?

Solution

The two groups don’t overlap, so add: $5 + 7 = 12$.

4. (Core) A Canadian postal code has the pattern letter, digit, letter, digit, letter, digit (like K1A 0B1). If any letter and any digit could be used in each spot, how many postal codes would be possible?

Solution

$$26 \times 10 \times 26 \times 10 \times 26 \times 10 = 17\,576\,000$$

(In real life, some letters aren’t used, so there are fewer.)

5. (Core) A phone PIN has $4$ digits.

• (a) How many PINs are possible?
• (b) How many have no repeated digits?

Solution

(a) $10 \times 10 \times 10 \times 10 = 10\,000$.

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

6. (Core) Six runners race (no ties). In how many ways can they finish? In how many ways can the gold, silver, and bronze medals be awarded?

Solution

All six places: $6! = 720$.

Just the top three: $6 \times 5 \times 4 = 120$.

7. (Core) How many odd three-digit numbers (from $100$ to $999$) have no repeated digits?

Solution

Fill the most restricted spots first. The last digit must be odd: $5$ choices ($1, 3, 5, 7, 9$). The first digit can’t be $0$ or the last digit: $8$ choices. The middle digit can be anything except those two: $8$ choices.

$$5 \times 8 \times 8 = 320$$

8. (Challenge) Solve $\dfrac{n!}{(n - 2)!} = 30$.

Solution

Cancel: $\dfrac{n!}{(n - 2)!} = n(n - 1)$. So $n(n - 1) = 30$, which gives $n^2 - n - 30 = 0$, or $(n - 6)(n + 5) = 0$. Since $n$ can’t be negative, $n = 6$.

Check: $6 \times 5 = 30$. ✓

9. (Challenge) How many whole numbers from $1$ to $999$ contain at least one digit $7$?

Solution

Count the opposite: numbers with no $7$. Write every number as three digits ($001$ to $999$, with leading zeros). Each digit has $9$ choices (anything but $7$), giving $9^3 = 729$ strings, but that includes $000$, which isn’t in the range. So $728$ numbers have no $7$.

$$999 - 728 = 271$$