1 Counting and Combinatorics

The puzzles in this chapter all share a single underlying question: in how many ways can a thing happen? That sounds simple, and for very small cases it is — you can list the possibilities by hand. But when the cases grow, hand-counting quickly becomes either tedious or wrong. That is exactly the moment where Python earns its keep.

Each section ends with a capstone: a puzzle whose answer we work toward as the section unfolds. By the time you reach the answer, you will have picked up the Python tools and the mathematical habit of thinking the puzzle requires.

The code cells in this chapter are live. You can edit them and press Run Code to run them right in your browser. (Nothing is sent anywhere. The first cell on a page takes a few seconds to load Python.) The cells share one session and are meant to be run top to bottom, like a notebook — a cell that uses target needs the cell that defined it to have run first.

1.1 Coin combinations

Capstone: Using pennies, nickels, dimes, and quarters, in how many ways can we form $1?

This is the puzzle that gave the book its name. Take a moment and guess the answer before reading further. Five? Fifty? Five hundred? Hold on to your guess — we’ll see how close you were.

1.1.1 What does “a way” mean?

Before we count ways, we have to be honest about what a “way” is.

Suppose you make 25 cents. One way is two dimes and a nickel. Another is one quarter. Another is twenty-five pennies. Another is one dime, two nickels, and five pennies. Each is a different combination of coins.

To pin this down, we’ll record each way as a tuple of four numbers:

(number of quarters, number of dimes, number of nickels, number of pennies)

So:

Two dimes and a nickel = (0, 2, 1, 0)
One quarter = (1, 0, 0, 0)
Twenty-five pennies = (0, 0, 0, 25)
One dime, two nickels, five pennies = (0, 1, 2, 5)

The puzzle becomes: how many tuples (q, d, n, p) of non-negative integers satisfy 25q + 10d + 5n + p = 100?

1.1.2 Try a smaller target by hand

Before we throw Python at $1.00, let’s do something smaller by hand. The trick to seeing how a puzzle works is to first solve a tiny version of it where you can list every case. So set the dollar aside for a moment: we are now making 10 cents, using only pennies, nickels, and dimes. A quarter is already worth more than the whole target, so it cannot appear in any answer — which is exactly the kind of shrinking that makes a puzzle small enough to do on paper.

Note

Pause and try. Grab a piece of paper. List every way to make 10 cents using pennies, nickels, and dimes. How many ways did you find?

Here is the full list, written as (q, d, n, p):

d	n	p	Total
0	0	10	10¢
0	1	5	10¢
0	2	0	10¢
1	0	0	10¢

Four ways.

Notice the pattern we used to make sure we didn’t miss anything:

We tried each possible number of dimes (0 or 1).
For each dime count, we tried each possible number of nickels.
The pennies just filled in whatever was left.

That’s the recipe. We systematically walked through possibilities, from the most valuable coin downward, letting the smallest coin (pennies) soak up the leftover. If you skipped any of those steps, you would either miss a way or count one twice.

Let’s do the next size up: 25 cents.

Note

Pause and try. Before reading the table, list every way to make 25¢ using pennies, nickels, dimes, and quarters. Use the same pattern: quarters first, then dimes, then nickels, then pennies.

q	d	n	p	Total
0	0	0	25	25¢
0	0	1	20	25¢
0	0	2	15	25¢
0	0	3	10	25¢
0	0	4	5	25¢
0	0	5	0	25¢
0	1	0	15	25¢
0	1	1	10	25¢
0	1	2	5	25¢
0	1	3	0	25¢
0	2	0	5	25¢
0	2	1	0	25¢
1	0	0	0	25¢

Thirteen ways.

Look closely at the table. Within each (q, d) pair, the nickel count counts up by 1 and the penny count counts down by 5 — because each nickel you add must remove five pennies’ worth of pennies. The whole table is just nested counting.

Here’s a number worth noticing: 4 ways for 10¢, 13 ways for 25¢. The count is growing fast. So fast that hand-counting will fail us soon.

1.1.3 Why we need code

What do you suppose 100¢ has? Five times 25¢ is 125, so maybe 125 ways?

That guess is going to be wildly off. Each new dime we allow gives another whole row of nickel choices, each new quarter gives another whole grid of dime-and-nickel choices, and so on. The numbers explode. By hand you’ll lose your place around 50¢ and have no chance at $1.

We need a system that doesn’t get tired. That system is a loop.

1.1.4 First Python: variables and arithmetic

Run this cell — press Run Code. It defines our problem.

We’ve made five variables — five names that point at integers. After running the cell, Python knows what quarter means.

A variable is just a label. We could write q = 25 or coin_one = 25, but quarter is friendlier when you read the code later. Naming things well is half of programming.

Tip

Try it. Click on the cell above, change target from 100 to 25, and run it again. The output updates. Now change it back to 100 so the rest of the cells in this section keep working.

Exercise 1: One-coin arithmetic

Below is a partly-finished cell. Replace each _____ with the right number, then run the cell. The output should be 20.

(Hint: 4 nickels means 4 × 5.)

1.1.5 A first loop

Now we want Python to systematically try things. The simplest loop in Python is a for loop with range.

range(0, 21) produces the numbers 0, 1, 2, …, 20 — twenty-one numbers in total. (In Python, the start is included and the stop is not. So range(0, 21) stops at 20.)

If we used only nickels, the most we could possibly use is 20, because 21 × 5 = 105, which is over our target. So the loop tries 0 through 20.

Read the output. The right column runs from 0 up to 100 in steps of 5. That is exactly what nickels do.

Tip

Why range(0, 21) and not range(0, 20)? In Python, range(a, b) goes from a up to but not including b. So range(0, 21) gives 0, 1, …, 20 — twenty-one numbers, ending at 20.

Exercise 2: Loops you write

Modify the loop below so that it prints the value, in cents, of 0 quarters, 1 quarter, 2 quarters, 3 quarters, and 4 quarters. (Why 4? Because 5 quarters is already more than $1.)

The right column should read 0, 25, 50, 75, 100.

1.1.6 Two loops, three loops

One loop is fine for nickels alone. But we have four kinds of coin. We need nested loops — a loop inside a loop.

Here is what it looks like to count over (quarters, dimes) at the same time. The outer loop fixes q. For each q, the inner loop runs through every allowed d.

There are 5 × 11 = 55 lines of output — one per (q, d) pair. Some of those pairs already exceed $1.00 (like q=4, d=10), and that’s fine for now. We’ll deal with that in a moment.

Now add a third loop, for nickels. Three nested loops mean we visit 5 × 11 × 21 = 1,155 combinations. That’s far too many to read, so we count all of them and print only the first 20.

Read those 20 lines and notice what doesn’t move: q and d are still 0 when the printing stops. The nickel loop has to run all the way through its 21 values before d can advance even once, and d has to finish all 11 of its values before q advances. Nested loops are an odometer — the rightmost wheel spins fastest, and each wheel to its left ticks over only when the wheel on its right completes a full turn.

The last line is the proof that the loops really did visit all 1,155 triples. We just declined to read them. That’s the leverage: the loops can search the whole space without us writing any of it out.

1.1.7 The mathematical insight: pennies are forced

Here is a question worth pausing on. We have four kinds of coin. Why are we using only three nested loops?

Because of a beautiful trick. Once we choose q, d, and n, the number of pennies has no choice left. If our target is 100 cents and the quarters, dimes, and nickels contribute some amount value, then the pennies must contribute exactly 100 - value. There’s nothing to decide.

So the only thing we need to check, for a given (q, d, n), is whether the value so far has overshot the target:

Is 25q + 10d + 5n ≤ 100?

If yes, this triple is one valid way (with pennies = 100 − 25q − 10d − 5n). If no, the pennies would have to be negative, which doesn’t make sense.

This is the math beat. We just turned a four-dimensional search into a three-dimensional one. That isn’t an efficiency hack — it’s a fact about the puzzle. Pennies are the slack variable. Whatever’s left over, they fill in.

Exercise 3: Spot the invalid triples

Run this cell. It looks at every (q, d, n) triple but prints only the ones that overshoot — where value is greater than 100, so the pennies would have to be negative. Fill in the missing condition.

(Hint: the condition compares value to 100 — which way does the inequality go?)

1.1.8 Counting up the answer

Now, instead of printing each triple, let’s just count the valid ones. The pattern is the same in every counting program:

Start a counter at zero.
Each time the loop finds what we’re looking for, add one.
Print the counter at the end.

1.1.9 The reveal

You should see this output:

Number of ways: 242

242 ways. That’s how many distinct combinations of pennies, nickels, dimes, and quarters add up to one dollar.

When was the last time you guessed 242 for anything? It’s a strange, specific number. And we now know exactly where it comes from: it is the count of integer triples (q, d, n) with q ≥ 0, d ≥ 0, n ≥ 0, and 25q + 10d + 5n ≤ 100. That set of triples is a finite slice of 3-dimensional space, and Python just walked through every point of it.

If your guess at the start was anywhere near 242, you should be a little suspicious of yourself.

1.1.10 A reusable function

What if we want to ask the same question for a different amount of money? We don’t want to copy and paste the loop every time. We want a function.

A function in Python is a named piece of code that takes inputs and gives back an answer. Here is one for our puzzle.

A few new pieces of Python here:

def introduces a function. The line def count_ways(target): says: “I’m defining a function called count_ways that takes one input named target.”
The body of the function is everything indented underneath.
return sends the answer back out.
// is integer division. 100 // 25 is 4. 103 // 25 is also 4 (the leftover is dropped). We use it to compute the largest possible number of each coin: at target 100¢, we can use at most 100 // 25 = 4 quarters.

Run the cell. The first three lines should match what we already know (4 ways, 13 ways, 242 ways). The $5.00 number is the surprise — coin combinations grow fast.

Exercise 4: Use the function

Use count_ways in the cell below to answer:

How many ways to make exactly $2.00?
How many ways to make exactly fifty cents?
How many ways to make exactly one cent? (Predict before running.)

1.1.11 One more dimension falls

We have an answer and a function that computes it. Let’s go back to the mathematics anyway, because there is a second insight sitting right where the first one was, and it is the better of the two.

Remember why pennies disappeared: once q, d, and n were chosen, the penny count was forced. Nothing to decide, nothing to loop over.

Now ask the same question one coin up. Once q and d are chosen, do we really have to loop over nickels?

Suppose we’ve fixed 1 quarter and 2 dimes. That’s 45 cents, leaving 55. Nickels can be 0, 1, 2, … up to 11, because 11 nickels is exactly 55. That’s 12 choices, and we didn’t have to visit them one at a time to know it — we just divided.

So the nickel loop isn’t a search. It’s a count, and counts have formulas.

Cleaner in fives

The arithmetic gets friendlier if we notice every coin except the penny is a multiple of 5. Our condition is

25q + 10d + 5n ≤ 100

and every term is divisible by 5, so divide the whole thing through:

5q + 2d + n ≤ 20

Same puzzle, smaller numbers. Read it as: quarters cost 5, dimes cost 2, nickels cost 1, and we have 20 to spend.

Now fix q and d, and let slack be what’s left over:

slack = 20 − 5q − 2d

If slack is negative, this (q, d) pair is already over budget and contributes nothing. Otherwise n may be anything from 0 to slack, which is slack + 1 choices.

That’s the whole reduction. No third loop:

242 again — but now in 55 steps instead of 1,155. We didn’t make the program cleverer. We did some of its work in advance, on paper.

It’s a sum, not a program

Written out, what that cell computes is a double sum:

\[\sum_{q=0}^{4} \ \sum_{d\,=\,0}^{\lfloor (20-5q)/2 \rfloor} (21 - 5q - 2d) \;=\; 242\]

Every piece of that expression came from somewhere you can point at: the outer limit 4 is “five quarters is too many,” the inner limit is “don’t overspend on dimes,” and the summand is the nickel count we just derived.

And an inner sum like that one is just an arithmetic series — consecutive terms falling by 2. Doing it in closed form collapses the dimes too, and leaves one term per quarter count:

242 = 121 + 72 + 36 + 12 + 1

Five numbers. You can add those in your head.

Tip

What those five numbers are. 121 is the number of ways to make a dollar using only dimes, nickels, and pennies — the q = 0 case. 72 is the number of ways to make the remaining 75 cents after one quarter is set down, 36 the ways to make 50 cents after two, and so on down to the single way to make nothing at all with four quarters.

So the answer splits by how many quarters you use, and each piece is a smaller version of the very same puzzle. That observation is the seed of a technique called dynamic programming, and of the generating-function method that solves coin problems for any coin set at all. Both are beyond us for now. The seed is not.

What this beat is really about

We solved this puzzle three times: with four loops’ worth of thinking, then three loops, now two. Each reduction came from the same move — noticing that a quantity we were about to search for could be computed instead.

That move is where mathematics pays a programmer. The loop was never wrong. It was just doing arithmetic one step at a time that we could do all at once.

Exercise 5: Check the reduction

The two-loop version should agree with count_ways for every target, not just 100. Fill in the blank so this compares them across several targets.

(Note the t // 5 where we had the literal 20. Dividing by 5 worked for 100 cents; think about why this still counts correctly when the target isn’t a multiple of 5.)

1.1.12 Reflection

What did we just do?

We translated an English puzzle (“how many ways to make a dollar in coins?”) into a precise mathematical question (“how many integer triples (q, d, n) satisfy 25q + 10d + 5n ≤ 100, with each variable ≥ 0?”), and then we used Python to enumerate the search space.

That recipe is general:

Define the search space — the set of all candidate answers.
Define what counts as valid — a condition each candidate must satisfy.
Count the valid ones — a counter starts at zero and grows.

Most of the puzzles in this book follow that three-step recipe in some form. The denominations may change, the condition may change, but the shape is the same.

A second thing worth noticing: the math did real work. The “pennies are forced” insight saved us a whole loop. Without it, our program would have been correct but wasteful, walking through penny counts that were already determined. Math and code together did better than either alone.

1.1.13 Stretch problems

Try as many of these as you like. They each tweak the puzzle and ask what changes.

A fifth coin: the half-dollar

The U.S. Mint has produced a 50-cent piece for over two hundred years. Add it as a fifth coin. How many ways to make $1 now? You’ll need either a fourth nested loop, or a clever rearrangement using the same “pennies are forced” trick. Try both.

No pennies allowed

Suppose you’ve lost all your pennies. How many ways to make exactly $1 using only nickels, dimes, and quarters?

This puzzle is harder than it looks: without pennies, not every target is reachable. (Try to make 7¢ using only nickels, dimes, and quarters. You can’t.) Modify count_ways so it requires the value to exactly match the target.

What’s the smallest target less than $1 that has zero ways under this rule? Try a few values until you find one.

At least one of each coin

How many ways to make $1 if your combination must include at least one penny, at least one nickel, at least one dime, and at least one quarter?

(Hint: change the starting value of each range. The pennies-are-forced trick still works, but the condition shifts.)

How does the count grow?

Make a list of count_ways(t) for t = 1, 2, 3, ..., 100 and look at how the answer grows. Is it linear? Quadratic? Cubic? (We’ll learn how to make plots in a later chapter — this is a puzzle to come back to.)

For now, you can at least print a few:

A different country’s coins

Old British currency had a 1-penny coin, a 3-penny coin, a 6-penny coin, a 1-shilling coin (12 pence), a 2-shilling coin (24 pence), a half-crown (30 pence), and so on, all the way up to a pound (240 pence). How many ways are there to make a pound under the old system?

(This is exactly the puzzle a 19th-century shopkeeper would have faced. The math was old before computers existed.)

1.2 Handshakes

Capstone: In a room of 30 people, everyone shakes hands once with every other person. How many handshakes happen in total?

Guess first, as always. Thirty people, each shaking twenty-nine hands — maybe 870? Or is that too big?

Hold the guess. This puzzle looks like the coin puzzle but rewards you differently, and the difference is the whole point of the section.

1.2.1 Start where you can count

Two people, Ana and Ben. They shake once. One handshake.

Three people, Ana, Ben, and Cleo. Ana-Ben, Ana-Cleo, Ben-Cleo. Three handshakes.

Four people — add Dev. Write them all out:

Ana-Ben	Ana-Cleo
Ana-Dev	Ben-Cleo
Ben-Dev	Cleo-Dev

Six handshakes.

Note

Pause and try. Add a fifth person, Eva, and list every handshake. Don’t count them in your head — write the pairs down. How many?

Ten. So our little table reads:

People	2	3	4	5
Handshakes	1	3	6	10

1.2.2 Why this puzzle is not the coin puzzle

Stop and look at 1, 3, 6, 10. Those numbers are suspiciously tidy.

That’s the tell. When a sequence comes out that clean, there is usually a formula hiding behind it — some expression you could feed 30 to and get the answer without listing a single handshake.

The coin puzzle wasn’t like this. We wanted the number 242, we looped our way to it, and we went home. Here the number is not the prize. The prize is the formula, and the reason it’s true.

That changes what the code is for. We are not going to write a loop to get an answer. We are going to write a loop to manufacture evidence — enough numbers, quickly enough, that the pattern becomes impossible to miss. Then we’ll guess the formula, check it, and finally explain it.

Brute force is the telescope here, not the destination.

1.2.3 What is a handshake, exactly?

Same discipline as the coins, where we had to pin down what “a way” meant.

Number the people 0, 1, 2, ... — Python counts from zero, so we will too. A handshake is a pair of two different people, and the pair is unordered: 0 shaking 1 is the same event as 1 shaking 0. There is no such thing as shaking your own hand.

Those two rules — different, and unordered — are the entire puzzle. Everything below is just teaching them to Python.

1.2.4 A first attempt, and what goes wrong

The obvious thing is two nested loops over everybody:

Sixteen lines, and both of our rules are broken.

Look for 0 shakes 0. Nobody shakes their own hand, but there it is — along with 1 shakes 1, 2 shakes 2, and 3 shakes 3. That’s 4 bad lines.

Now find 0 shakes 1. Then find 1 shakes 0. Both are printed. They are the same handshake, written from the two participants’ points of view. Every real handshake in that output appears twice.

So 16 lines = 4 impossible ones + 12 real-but-doubled ones, and 12 ÷ 2 = 6. Six, which is the answer we got by hand. The loop had the right idea and the wrong bookkeeping.

1.2.5 One bound fixes both rules

We could patch this with an if, but there’s a cleaner move. Insist that the second person’s number is always larger than the first:

Six lines. Exactly the six pairs from the table, in order.

Read range(i + 1, people) again, because it is new. Until now every range we wrote had fixed numbers in it. This one starts at i + 1 — the inner loop’s bounds depend on the outer loop’s variable. As i walks forward, the inner loop gets shorter:

`i`	`j` runs over	pairs
0	1, 2, 3	3
1	2, 3	2
2	3	1
3	(nothing)	0

3 + 2 + 1 + 0 = 6. The loop is walking a triangle, not a square. Hold on to that word; it comes back.

Tip

Why j > i means “unordered”. Of the two ways to write a handshake — 0 shakes 1 and 1 shakes 0 — exactly one has the second number bigger. By demanding j > i we pick that one and throw the other away. We’re not counting differently; we’re just refusing to write the same handshake twice.

This is the same move we made with the coins, where we fixed an order on (q, d, n) so that “two dimes and a nickel” couldn’t sneak in again as “a nickel and two dimes.” Choosing a canonical order is the standard cure for double counting.

Exercise 1: Set the bound yourself

Fill in the blank so this prints each handshake exactly once, with no one shaking their own hand. (You should get 10 lines for 5 people.)

1.2.6 Answering the capstone

Swap printing for counting, and stop at nothing:

435. Not 870 — that was the double count, the same trap the very first loop fell into.

And now we ignore that number, because we came for the formula.

1.2.7 The hunt: manufacture evidence

One data point teaches nothing. Wrap the whole count in a third loop and get a whole table at once:

2 people --> 1 handshakes
3 people --> 3 handshakes
4 people --> 6 handshakes
5 people --> 10 handshakes
6 people --> 15 handshakes
7 people --> 21 handshakes
8 people --> 28 handshakes
9 people --> 36 handshakes
10 people --> 45 handshakes

This is what the brute force was for. Nine data points in under a second, every one of them certainly correct, because the loop is a direct transcription of the rules.

Note

Pause and try. Before reading on, stare at 1, 3, 6, 10, 15, 21, 28. Two questions. First: how much does each number add to the one before it? Second: can you predict the entry for 11 people without running anything?

1.2.8 First pattern: the newcomer

The gaps are 2, 3, 4, 5, 6, 7 — going from 9 people to 10 adds 9.

That one you can explain on the spot. When a new person walks into a room that already has everyone acquainted, they shake hands with each person present and nobody else. Ten people in the room means the eleventh arrival makes exactly 10 new handshakes. Nothing else changes; the handshakes that already happened stay happened.

So the answer for 30 people is

1 + 2 + 3 + … + 29

one term per arrival. That is already a real result, and you can check it:

Exercise 2: Add up the arrivals

Fill in the blanks so this sums 1 + 2 + … + 29. It should print 435, matching the double loop above.

1.2.9 Second pattern: the doubling trick

Summing 29 numbers is honest work, but it is still work. We want a formula — one multiplication, no loop.

The obstacle is that 1, 3, 6, 10, 15 don’t factor into anything friendly. So try a trick that looks like cheating and isn’t: double them.

2 people --> 2
3 people --> 6
4 people --> 12
5 people --> 20
6 people --> 30
7 people --> 42
8 people --> 56
9 people --> 72
10 people --> 90

Now read them as products:

People	Doubled	Factors
2	2	1 × 2
3	6	2 × 3
4	12	3 × 4
5	20	4 × 5
6	30	5 × 6

Every doubled value is the number of people times one less than the number of people. Undouble it and you have the formula:

handshakes = people × (people − 1) ÷ 2

Check it against 30 in your head: 30 × 29 = 870, halved is 435. That’s our number.

1.2.10 Why the doubling worked

A guessed formula that matches nine data points is a good conjecture, not an explanation. Here is the explanation, and it is the reason the doubling trick worked at all.

Count the handshakes from each person’s point of view. Each of the 30 people shakes hands with everyone except themselves — 29 handshakes each. Multiply: 30 × 29 = 870.

But 870 is not the number of handshakes. It is the number of hands involved, or if you prefer, the number of handshakes counted twice — once by Ana when she shakes Ben’s hand, and again by Ben when he shakes Ana’s. Every handshake has exactly two participants, so every handshake got counted exactly twice.

Divide by two. 435.

That argument — count something the easy way, notice you counted each thing the same number of times, divide — is called double counting, and it is one of the sharpest tools in combinatorics. The doubling we did on screen was this argument run backwards: we multiplied by 2 precisely because that undoes the division, turning the tidy-but-opaque 435 back into the obvious 30 × 29.

Tip

The same fact, three ways. We now have three routes to 435: list every pair with the j > i loop; add up the arrivals, 1 + 2 + … + 29; or multiply 30 × 29 and halve it. They agree because they are three descriptions of the same set of pairs. When three independent methods give one answer, you are not hoping any more — you know.

1.2.11 Verify the formula against the brute force

Never trust a formula you haven’t tested against the thing it replaces. This cell computes both and prints them side by side:

Two columns, nine rows, no disagreement.

Tip

Why // and not /? In Python, / gives a decimal: 30 / 2 is 15.0, with a point-zero. // divides and keeps a whole number: 30 // 2 is 15. We want a count of handshakes, and there is no such thing as half a handshake. Using // also quietly asserts something true: people × (people − 1) is a product of consecutive integers, so one of them is even and the halving always comes out exact.

1.2.12 What the formula buys

The loop and the formula agree, so why prefer the formula? Because they cost wildly different amounts. Count a thousand people the slow way:

That took a moment — Python just ran the inner line about half a million times. Now the same answer:

Instant. And for a million people the loop would run for hours while the formula still answers immediately. That is what deriving a formula is worth: not elegance for its own sake, but the difference between a computation you can do and one you can’t.

The loop was never wasted, though. Without it we would have had no table, without the table no pattern, and without the pattern no formula to test.

1.2.13 Reflection

Look back at what happened, because the shape of it matters more than the number 435:

We counted small cases by hand until a pattern was plausible.
We wrote a brute force whose only job was to be obviously correct, and used it to generate a table.
We read a conjecture off the table — first the newcomer rule, then, after the doubling trick, the formula.
We explained why the formula had to be true, by double counting.
We tested the formula against the brute force before trusting it.

Steps 2 and 5 are the programmer’s contribution; steps 1, 3, and 4 are the mathematician’s. Neither one gets you the whole way.

One last thing. The quantity you just derived has a name: it is the number of ways to choose 2 things from n when order doesn’t matter, written C(n, 2) and read “n choose 2.” You will meet its siblings — C(n, 3), C(n, 4) — the moment you start counting committees, poker hands, or lottery tickets. You found the first one yourself, out of a table of handshakes.

1.2.14 Stretch problems

Everybody plays everybody, twice

A round-robin league has 12 teams. Every pair plays a home game and an away game. How many games in the season? (Careful: this puzzle wants the ordered pairs, so it is the count before we divided by two.)

Triangles

Three people in a room might form a trio — a set of three, all of whom know each other. Extend the idea: how many ways are there to choose a group of three people from 30?

Fill in the bounds so each trio is counted once, in increasing order:

For 6 people you should get 20. Then build the table for 2 through 10 people, hunt for the pattern the same way we did above, and see whether you can guess the formula. (Hint: try multiplying by 6 instead of 2.)

The polygon’s diagonals

A convex polygon with 12 corners has some sides and some diagonals. Every pair of corners is joined by exactly one of the two. How many diagonals does it have?

Gauss’s shortcut

Legend says a schoolboy named Gauss was told to add 1 + 2 + … + 100 and answered almost immediately. He paired the first with the last (1 + 100), the second with the second-to-last (2 + 99), and noticed every pair sums to 101. How many pairs are there, and how does his trick give the same formula we derived for handshakes?

1.3 Stair climbing

Capstone: In how many ways can we climb a staircase of 10 stairs if at each step we may go up either one stair or two?

Ten stairs. At each move you take one stair or two, your choice, and you keep going until you’re at the top. Two climbs are different if you’d notice the difference while doing them.

Guess. Ten? Twenty? A hundred?

1.3.1 Order matters here — and it didn’t before

Before counting anything, notice how this puzzle differs from the two we’ve already solved. It is the difference that makes it interesting.

With coins, “two dimes and a nickel” was one way. It didn’t matter which coin you put down first; you ended up with the same handful. With handshakes, Ana-Ben and Ben-Ana were the same handshake, and we worked hard — the j > i trick — to keep from counting it twice.

Stairs are the opposite. Climbing 1 then 2 is not the same climb as 2 then 1. Your feet land in different places. Both get you to stair 3, and both count separately.

Tip

Combinations and sequences. When order doesn’t matter, you’re choosing a set — a handful of coins, a pair of people. When order does matter, you’re building a sequence. They are counted by different tools, and the first question to ask about any counting puzzle is which one you’re in.

Mixing them up is the most common way to get a counting problem wrong, in either direction: counting 1,2 and 2,1 once when they should be twice, or twice when they should be once.

1.3.2 Start where you can count

One stair. One way: a single small step. 1 way.

Two stairs. Either two small steps, or one big one: 1,1 or 2. 2 ways.

Three stairs. 1,1,1, 1,2, 2,1. 3 ways.

Four stairs. 1,1,1,1, 1,1,2, 1,2,1, 2,1,1, 2,2. 5 ways.

Note

Pause and try. Write out every way to climb five stairs. Be systematic — start with all the climbs that begin with a 1, then the ones that begin with a 2. How many?

Eight. Our table:

Stairs	1	2	3	4	5
Ways	1	2	3	5	8

1, 2, 3, 5, 8. Tidy again — and if you followed the hint in that callout, you may already suspect where the tidiness comes from.

1.3.3 Why our old tools don’t fit

In the coin puzzle we knew, before writing a line, that there were exactly three things to loop over: quarters, dimes, nickels. Three quantities, three nested loops.

Try that here. How many loops do you need for ten stairs?

You don’t know. A climb might be ten moves long (all ones) or five moves long (all twos) or anything between. The number of decisions is itself unknown, so there is no fixed stack of for loops to write. Our one technique has run out.

We need a genuinely new idea, and the hint in the Pause-and-try callout is exactly it.

1.3.4 Look at the first step

Stand at the bottom of ten stairs. You are about to move. You have exactly two choices, and every possible climb begins with one of them:

You step up one stair. You’re now standing on stair 1, facing a staircase with 9 stairs left. The rest of your climb is a way of climbing 9 stairs.
You step up two stairs. You’re on stair 2, with 8 left. The rest of your climb is a way of climbing 8 stairs.

Those two cases can’t overlap — a climb starts with a 1 or a 2, never both — and nothing else is possible. So

ways(10) = ways(9) + ways(8)

and nothing about 10 was special:

ways(n) = ways(n − 1) + ways(n − 2)

Tip

You have seen this move before. In the coin section we split 242 by how many quarters were used — 242 = 121 + 72 + 36 + 12 + 1 — and each piece was the same puzzle on a smaller target. Here we split by the first step, and each piece is the same puzzle on a shorter staircase.

Split the possibilities by one decision, and ask the same question about what’s left. That is the idea this whole section is built on, and it will outlast every Python trick in this book.

Check it against the table: 1, 2, 3, 5, 8. Indeed 3 = 2 + 1, 5 = 3 + 2, 8 = 5 + 3. Every entry is the sum of the two before it.

1.3.5 Where the staircase ends

A rule that defines ways(n) using ways(n−1) and ways(n−2) has to stop somewhere, or it will chase itself down past zero forever. So we need starting values.

ways(1) = 1 is clear enough: one stair, one small step.

ways(0) = 1 is the strange one. How many ways are there to climb no stairs? The answer is one: stand still. You are already at the top; the climb consisting of no steps at all is a perfectly good climb, and it is the only one.

Note

Why the empty climb counts. This isn’t a technicality invented to make the formula work — it’s what the formula was already telling us. We said ways(2) = ways(1) + ways(0), because a two-stair climb either starts with a 1 (leaving one stair) or with a 2 (leaving none). We know by hand that ways(2) = 2 and ways(1) = 1. So ways(0) has to be 1.

Taking two stairs at once, from the bottom of a two-stair staircase, is one climb. Counting the “nothing left to do” case as one possibility is what records it.

1.3.6 Teaching Python to call itself

Here is the rule, written as Python. Look at it before you run it:

89.

Read the function again, because something genuinely new just happened. ways calls ways. A function, in the middle of being defined, uses itself. That is called recursion, and it is not a trick — it is the most direct possible translation of the rule we derived. Compare them:

ways(n) = ways(n − 1) + ways(n − 2)

return ways(stairs - 1) + ways(stairs - 2)

The math and the code are the same sentence.

The if stairs <= 1 line is what stops the chase: it covers both ways(1) and ways(0), and it is the reason the function eventually returns instead of calling forever.

Tip

How does that not run forever? Every call passes a smaller number than it received. ways(10) waits on ways(9) and ways(8); ways(9) waits on ways(8) and ways(7); and so on down. Since the numbers only shrink, every chain eventually hits 1 or 0, returns a plain 1, and the sums unwind back up.

A recursive function needs both halves — a case that gets smaller, and a case that stops. Leave out either one and it never finishes.

Exercise 1: Climb a taller staircase

Predict the answers before running: if 10 stairs give 89, what do 11 and 12 give? (Use the rule: each is the sum of the two before it.)

1.3.7 The reveal: an old friend

Print the whole sequence and look at it properly:

0 stairs --> 1 ways
1 stairs --> 1 ways
2 stairs --> 2 ways
3 stairs --> 3 ways
4 stairs --> 5 ways
5 stairs --> 8 ways
6 stairs --> 13 ways
7 stairs --> 21 ways
8 stairs --> 34 ways
9 stairs --> 55 ways
10 stairs --> 89 ways
11 stairs --> 144 ways
12 stairs --> 233 ways

Those are the Fibonacci numbers, described by Leonardo of Pisa in 1202 in a puzzle about breeding rabbits, and turning up ever since in pinecones, sunflower seed spirals, and — as you have just discovered — staircases.

We didn’t go looking for them. We asked an honest question about stairs, split it by the first step, and Fibonacci fell out. That happens a lot. A sequence that shows up in unrelated places is usually a sign that the same structure is hiding in all of them, and here the structure is exactly the rule we derived: each thing is built from the two before it.

1.3.8 What recursion costs

The function is short, correct, and quietly wasteful.

The trouble is that ways(10) calls ways(9) and ways(8); but ways(9) also calls ways(8). Two separate calls compute the same thing, and neither knows about the other. Further down the damage compounds: a single ways(10) reaches ways(2) thirty-four separate times, and bottoms out at ways(1) fifty-five times. Every one of those is the same trivial question, asked again from scratch.

How much work is that? Count it with a function shaped exactly like the first, except it counts calls rather than climbs — one for itself, plus whatever its two children cost:

Put the two columns side by side and a pattern appears immediately: calls = 2 × ways − 1. To compute 89, the function called itself 177 times.

That sounds survivable until you remember that ways grows exponentially. For 50 stairs the answer is about 20 billion, so the naive function would call itself about 40 billion times to produce it. Your browser would still be working on it next week.

Note

Feel it, briefly. This cell is deliberately slow — it recomputes the same small staircases millions of times. Expect a real pause.

That pause is not Python being slow. It’s our method being wasteful.

1.3.9 Building a table instead

The waste has an obvious cure. We keep recomputing ways(5) because we throw the answer away each time. So let’s keep it.

Work upward instead of downward: start from what we know, and build each new entry from the two already sitting there. For that we need somewhere to put them — a list.

Three new pieces of Python, all of them earned:

[1, 1] is a list — an ordered row of values, written in square brackets. This one holds our two known answers, ways(0) and ways(1).
table[stairs - 1] reads the entry at a position. Positions count from 0, so table[0] is the first entry. That’s why ways(0) living at position 0 is so convenient: the index is the number of stairs.
.append(...) adds a new value to the end of the list.

The loop never looks backwards more than two places, and it never computes anything twice. Ten stairs costs nine additions.

Tip

Same rule, opposite direction. The recursive version starts at 10 and works down, asking “what would I need to know?” The table version starts at 0 and works up, answering “what do I already know?” Both implement ways(n) = ways(n−1) + ways(n−2). Only the direction of travel changed, and with it the cost: exponential became one pass.

Storing results so they’re computed once rather than repeatedly is the core of a technique called dynamic programming. You met its seed in the coin section, when 242 split into five smaller versions of itself. Here it is doing real work.

Exercise 2: Fifty stairs

The table version can do in an instant what the recursive one couldn’t do in a week. Fill in the blanks to build the table all the way to 50.

(Careful with the loop’s stopping value. To end up with an entry at position 50, how far does range have to go?)

1.3.10 Verify the two against each other

Two methods, one answer — so they had better agree everywhere, not just at 10:

Twenty-one rows, no disagreement. The slow method is the one we trust — it’s a direct transcription of the rule — so agreeing with it is exactly what earns the fast method its keep.

1.3.11 Reflection

This section introduced the first idea in the book that isn’t about loops.

We noticed the puzzle counts sequences, not sets, and that 1,2 and 2,1 are different climbs.
We found that our nested-loop technique could not be applied at all, because the number of decisions wasn’t known in advance.
We split the possibilities by one decision — the first step — and found the same puzzle waiting on the other side, smaller.
We wrote that rule directly as a recursive function, and got Fibonacci without asking for it.
We measured what the recursion cost, found it doubling the answer’s own exponential growth, and fixed it by building a table upward instead of chasing downward.
We checked the fast method against the slow, obviously-correct one.

Step 3 is the one to carry with you. Splitting a problem by a single decision and recognising what remains is the most portable idea in this chapter — more portable than the coin loops, more portable than j > i.

1.3.12 Stretch problems

A longer stride

Suppose you can climb one, two, or three stairs at a time. Re-derive the rule by asking what the first step could be, then adapt the table. How many ways to climb 10 stairs now?

(You should get 274. And check the starting values yourself — why is table[2] equal to 2 rather than 3?)

Count the big steps

Every climb of 10 stairs uses some number of 2s — maybe none, maybe as many as five. Group the 89 climbs by how many 2s they contain.

A climb with k twos uses 10 − 2k ones, so it has 10 − k steps in total, and choosing which of those steps are the 2s is a choose problem — the same kind you solved in the handshakes section. The count is C(10 − k, k), and those numbers are

1, 9, 28, 35, 15, 1

which sum to 89. Verify that sum, then check the same idea works for a staircase of 6 (you should get 1, 5, 6, 1 adding to 13).

A broken stair

Stair number 7 is rotted through and cannot be stepped on. How many ways are there to climb the 10 stairs now? (Hint: what is ways(7) if you can’t stand on stair 7?)

The golden shortcut

Fibonacci numbers have a closed form, built from the golden ratio φ = (1 + √5) / 2. The n-th one is the nearest whole number to φⁿ / √5. Look it up, try it for a few values, and consider: our table takes n additions and the closed form takes none — but the closed form needs irrational arithmetic, and computers store those approximately. Which would you trust for the 1000th Fibonacci number?