Counting

What this move does

Counting has just one rule: count every object exactly once. Miss nothing, and count nothing twice. Four tools are enough:

steps \to multiply cases \to add repeats \to divide overlaps \to subtract

If a job is done in steps, one after another, multiply the numbers of choices at each step (the multiplication principle). In the tree above, each new level multiplies the number of leaves.
If a job splits into cases that do not overlap, add the counts of the cases (the addition principle).
If every object has been counted $k$ times, divide the total by $k$ .
If the cases overlap, subtract what was counted too often (inclusion–exclusion).

Predict first

To get to the museum you can take a bus (any of $3$ routes) or the metro (any of $2$ lines). When you arrive, you go in through one of $2$ entrances. How many ways are there in all?

3 + 2 + 2 = 7

ways

(3 + 2) \times 2 = 10

ways

3 \times 2 \times 2 = 12

ways

3 \times 2 + 2 = 8

ways

Choose an answer first; then you can see the result.

Work through one: standing in line

Choose $3$ of the $4$ people A, B, C, D and line them up for a photo. How many different lineups are there?

Example: choose 3 of 4 people and line them up

Step 1 / 5

Break the job into steps
The line has three places. First decide who stands on the left, then in the middle, finally on the right. These are steps, so we multiply. Right now the tree is just a root.
Step 1: the left
Step 2: the middle
Step 3: the right
Each leaf is one lineup

Look again at the reason for step 2. Which people you can choose depends on step 1 (if A is on the left, the middle is B, C or D), but how many you can choose is always $3$ . The multiplication principle only needs the number to stay the same.

(The Chinese book writes the number of permutations of $3$ out of $4$ as $A_{4}^{3}$ ; many English books write $P (4, 3)$ or $_{4} P_{3}$ .)

Counted too often: divide

What if you just choose $2$ people for cleaning duty, and order does not matter? “A, B” and “B, A” are the same pair.

Below, the left side shows every ordered lineup and the right side shows the truly different groups. Tap any card to see how many “twins” it has on the left.

Every group appears exactly

2

times on the left, so the number of groups is

12 \div 2 = 6

. Change “Choose” to

3

: how many times does each group appear now?

Predict first

Choose $3$ of $5$ people to form a group (order does not matter). There are $5 \times 4 \times 3 = 60$ ordered lineups. How many groups are there?

groups

Choose an answer first; then you can see the result.

The same idea handles people “sitting in a circle”. $4$ people sit around a round table, and rotating everyone counts as the same seating:

With numbered seats there are

4! = 24

seatings. Rotating a round-table seating

4

times gives

4

different cards, so there are

24 \div 4 = 6

seatings.

Counting routes through the streets

Walk from A to B, moving only right or up. A route to any crossing makes its last step either from the left or from below. The two cases do not overlap, so

routes to this crossing = routes to its left neighbor + routes to the neighbor below .

Predict first

Start with a small one: a block of streets $2$ squares wide and $2$ squares high. Going from the bottom-left corner to the top-right corner (only right or up), how many routes are there?

routes

Choose an answer first; then you can see the result.

Here is another way to see it. On a grid $4$ squares wide and $3$ high, every route takes exactly $7$ steps, and $3$ of them go up. Once you choose which $3$ steps go up, the route is fixed, so the number of routes is $C_{7}^{3} = 35$ : the same answer as adding square by square.

Example: one crossing in the middle is closed for roadwork

Step 1 / 5

Write 0 at the roadblock
Crossing $(2, 1)$ is closed: no route through it counts, so its number is $0$ . The bottom row and the left column are still all $1$ .
Add as usual
Right of the roadblock
Keep adding to the end
Check by subtracting

Counted too much: subtract

How many numbers from $1$ to $30$ are a multiple of $2$ or a multiple of $3$ ? The two cases overlap, and adding them directly counts the overlap twice.

In the picture below, choose “add” or “subtract” for each term. The small tag next to a number tells you how many times it is counted right now. The goal: every number inside the circles is counted exactly once.

Start by adding just

∣ A ∣

and

∣ B ∣

, and see which numbers get counted

2

times.

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

With three sets there is one more layer. Try it yourself first:

Predict first

How many numbers from $1$ to $30$ are a multiple of at least one of $2$ , $3$ , $5$ ?

31

21

22

20

Choose an answer first; then you can see the result.

When it fails

“Counted too often, so divide” needs one thing: every object must be counted the same number of times.

Break it

Counterexample lab: remove one condition

Conclusion: total ÷ number of repeats = the true count

Make three-letter “words” from the letters A, A, B. First treat the two A's as different, A₁ and A₂: there are $3! = 6$ orders. Each word is counted $2$ times, so there are $6 \div 2 = 3$ words.

Practice

Exercise 1Basic

A school lunch combo is one of $4$ main dishes, one of $3$ soups and one of $2$ fruits. How many different combos are there?

Exercise 2Basic

$6$ teams play a round robin (every two teams play each other exactly once). How many games are played in all?

Exercise 3Advanced

On a grid of streets $5$ squares wide and $3$ high, walk from the bottom-left corner A $(0, 0)$ to the top-right corner B $(5, 3)$ , moving only right or up. Crossing $(2, 2)$ is closed for roadwork and cannot be used. How many routes are there?

Exercise 4Advanced

How many numbers from $1$ to $100$ are neither a multiple of $2$ nor a multiple of $5$ ?

Exercise 5Challenge

Using the digits $0, 1, 2, 3, 4$ without repeating any digit, how many three-digit even numbers can you make?

What this move does

Work through one: standing in line

Example: choose 3 of 4 people and line them up

Counted too often: divide

Counting routes through the streets

Example: one crossing in the middle is closed for roadwork

Counted too much: subtract

When it fails

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Adding when you should multiply

Counting every handshake twice

Adding two cases that overlap