Unit 25: Counting Cleverly

One decision after another

You have 3 shirts and 4 pairs of trousers. How many outfits?

For each of the 3 shirts there are 4 choices of trousers, so there are 3 × 4 = 12.

That is the multiplication principle: when choices happen one after another, multiply them. Almost all of counting comes from this one sentence.

When you cannot reuse

Now say the letters may not repeat. The first can be any of 4, but once it is used the second has only 3 left.

So it is 4 × 3 = 12, not 16.

The multiplication principle still works — you just have to notice that the second number shrank.

Factorials count arrangements

Arranging 5 books on a shelf: 5 choices for the first slot, 4 for the next, then 3, 2, 1.

5 × 4 × 3 × 2 × 1 = 120, written 5! and said five factorial.

Factorials get huge fast. 10! is already over three million.

Choosing some, in order

Out of 8 runners, how many ways can gold, silver and bronze be given out?

8 choices for gold, 7 for silver, 6 for bronze: 8 × 7 × 6 = 336.

That is a permutation — choosing some things where the order matters. You simply stop multiplying early.

Be systematic, not clever

Before any formula, learn to list properly. Fix the first thing, run through all the seconds, then move on.

For two-digit numbers from 1, 2, 3 with no repeats: 12, 13, then 21, 23, then 31, 32. Six of them.

Going in order is what guarantees you missed nothing. Jumping about is what guarantees you did.

A tree keeps track for you

Draw a branch for each first choice, then branches off each of those for the second, and so on.

Every complete path from the trunk to a leaf is one outcome, and the leaves count themselves.

A tree is slow for big numbers, but it never lies — and it is how you check a formula you are not sure about.

Identical letters need dividing out

How many arrangements of the letters in EGG?

If the two Gs were different you would say 3! = 6. But they are not, so every arrangement has been counted twice — once for each way of ordering the Gs.

So the answer is 6/2 = 3: EGG, GEG, GGE. Divide by the factorial of each repeat.

Overcounting is the whole idea

Notice what happened: count as if everything were different, then divide by how many times you counted each thing.

That is the same move that gave combinations from permutations. It will give the answer to almost every hard counting problem you meet.

Count loosely, then correct. Trying to count exactly the first time is far harder.

Glue them together

Four people in a row, but Amy and Ben must sit together.

Treat the pair as one block. Now there are three things to arrange: 3! = 6 ways. Then Amy and Ben can swap inside their block, doubling it.

So 6 × 2 = 12. Gluing, then allowing for the inside order, handles every "must be together" question.

Count the opposite instead

Now: Amy and Ben must not sit together.

Counting that directly is fiddly. So count all the arrangements, then take away the ones where they *are* together.

24 - 12 = 12. Whenever a condition says "not", try counting its opposite — it is almost always easier.

A row of choose numbers

Write out choose(4, k) for k from 0 to 4: 1, 4, 6, 4, 1.

Symmetric, because choosing who is in is the same as choosing who is out. And each number is the sum of the two above it in the previous row — that is Pascal’s triangle.

The row also adds to 2^4 = 16: every possible subset of four things.

Choosing from two groups at once

A team of 2 boys and 2 girls from 5 boys and 4 girls.

Choose the boys: choose(5, 2) = 10. Choose the girls: choose(4, 2) = 6. The two choices are independent, so multiply: 60.

Combinations inside each group, multiplication principle between them. That pairing solves most real selection problems.

Every number is the two above it

Start with a 1. Each new row begins and ends with 1, and every other entry is the sum of the two above it.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

That is Pascal’s triangle, and the numbers in it are exactly the choose numbers from the last lesson.

Why adding the two above works

To choose 2 people from 5, look at whether the newest person is in your group.

If they are, you need 1 more from the other 4: choose(4, 1).
If they are not, you need 2 from the other 4: choose(4, 2).

Every group falls into exactly one case, so choose(5,2) = choose(4,1) + choose(4,2). The triangle’s rule is a counting argument, not a coincidence.

It expands brackets too

Multiply out (x + 1)^4 and you get x^4 + 4x^3 + 6x^2 + 4x + 1.

Look at those numbers: 1, 4, 6, 4, 1. The fourth row of the triangle, exactly.

So the same numbers count committees *and* expand brackets — because each term of the expansion is a choice of which brackets contribute an x.

Count them all, then divide

Choosing 3 people from 8 for a team is different from handing out medals — the same three people are one team however you order them.

So count the ordered ways, 8 × 7 × 6 = 336, then divide by the 3! = 6 orders each team was counted in.

336 ÷ 6 = 56. That is a combination, written choose(8, 3).

Choosing who is out

Picking 4 from 6 to be in is the same as picking 2 to be out. So choose(6, 4) and choose(6, 2) are equal — both 15.

That symmetry is often the quickest route: choosing 48 from 50 sounds terrible, but choosing 2 to leave out is easy.