Counting & Probability — Count carefully. Don't compute.

Try this in your head: write down every way to arrange the letters A, B, C in a row. If you scribble them as they pop up — ACB, BAC, ABC, CBA… — you will lose track and either miss one or write one twice. Now do it again, but force yourself to go in alphabetical order:

• ABC, ACB
• BAC, BCA
• CAB, CBA

Six. And you know it is six, because you marched through it: A first (two ways), then B first (two ways), then C first (two ways). The order did the bookkeeping for you.

That is the entire skill. For a small count, the smartest tool is not a formula — it is writing them all out in a fixed order. The list never lies. The danger was never that listing is slow; it is that a random list double-counts and skips. A systematic one cannot.

(This particular list is also 3! = 3 × 2 × 1 = 6, the factorial you will meet in chapter 8. For small numbers, the list is clearer than any formula — and it is its own proof.)

Counting digits, not numbers — the page-number trick

A book has pages numbered 1, 2, 3, … up to 150. How many digits get printed in all those page numbers?

Your instinct is to write them all out and count. 150 numbers, each 1 to 3 digits long — that’s a wall of typing. Resist it. The trick: group the pages by how many digits each one uses, and listing collapses into three quick multiplications.

• 1-digit pages (1–9): that’s 9 pages, 1 digit each → 9 × 1 = 9 digits.
• 2-digit pages (10–99): that’s 90 pages, 2 digits each → 90 × 2 = 180 digits.
• 3-digit pages (100–150): that’s 150 − 100 + 1 = 51 pages, 3 digits each → 51 × 3 = 153 digits.

Add the groups: 9 + 180 + 153 = 342 digits. No wall of typing.

(Watch the page count in that last group. From 100 to 150 there are 51 pages, not 50 — count both ends. The classic slip is forgetting the + 1.)

Running it backwards

The harder version hands you the digit total and asks for the page count. “A book’s page numbers use 270 digits. How many pages?” Peel off the blocks in order:

• Pages 1–9 eat 9 digits. Left: 270 − 9 = 261.
• Pages 10–99 eat 180 more. Left: 261 − 180 = 81.
• The rest are 3-digit pages: 81 ÷ 3 = 27 of them (pages 100–126).

So the book has 99 + 27 = 126 pages. Same blocks, subtracting your way down instead of adding up.

To count digits across many numbers, group by digit-length first — never write them all out.

Counting a plain list — slide it down to start at 1

How many whole numbers are in the list 9, 10, 11, …, 27? The list does not start at 1, so the last number is not the count. But here is a move that makes it start at 1: subtract 8 from every number. The list slides to 1, 2, 3, …, 19 — same length, and now the last number is the count. So there are 19 numbers.

Sliding the list never changes how many entries it has, so this always works. It gives the formula every counter should own:

Now put it beside the bogus “span ÷ step” from the box below. For multiples in a range, slide them onto 1, 2, 3, … the same way. How many multiples of 4 lie between 25 and 101?

• Smallest multiple of 4 that is at least 25: since 24 = 4 × 6 is too small, it is 4 × 7 = 28.
• Largest multiple of 4 that is at most 101: 4 × 25 = 100.
• So the list is 28, 32, …, 100. Divide every term by 4 to get 7, 8, …, 25 — an ordinary list. Count it: 25 − 7 + 1 = 19 multiples.

The recipe: find the first multiple at or above the low end, the last at or below the high end, divide both by the step, then apply b − a + 1. That positive method is what the bogus shortcut below is faking — and unlike the shortcut, it never misses an endpoint.

Framing inspired by AoPS Prealgebra.

(Digit-counting / page-numbering idea adapted from Problem Solving via the AMC, Australian Maths Trust.)

If you make a series of choices, and each choice's count is independent of the others, the total number of outcomes is the product of the counts.

Why does it work? Picture a tree. Each level is one choice. The first choice has m₁ branches; each of those splits into m₂ branches; each of those into m₃; and so on. The total number of leaves at the bottom is the product.

3 shirts × 4 pants — three branches, each splitting into four.

Add 2 hats and each leaf splits again: 3 × 4 × 2 = 24 outfits.

When the count changes after each step. If picking the second item depends on the first — say, you can't pick the same item again — then the count of choices shrinks at each step. For a 3-letter sequence from {A, B, C, D, E} with no letter repeated:

• 1st letter: 5 choices.
• 2nd letter: 4 choices (anything except the first).
• 3rd letter: 3 choices (anything except the first two).

Total: 5 × 4 × 3 = 60.

This shrinking-pool pattern is called a permutation (chapter 8 has more).

Arranging in a circle

Five friends in a row: 5! = 120 orders. Now seat them around a round table. You get fewer — here's why.

A circle has no “first seat.” The order ABCDE is the same as BCDEA, CDEAB, DEABC, EABCD — spin the table and nobody has moved relative to anyone else. Every circular seating got counted 5 times inside that 120.

So divide it out: 5! ÷ 5 = 24 seatings.

THE MOVE: at each step ask “how many options do I have right now?” — then multiply.

(Circular-arrangement idea adapted from Problem Solving via the AMC, Australian Maths Trust.)

Count the people in a room who are not wearing a hat. Easy — you glance around and tally the bare heads. Now count the people who are wearing one… the same room, but suddenly you are squinting at every cap and beanie. Same room, two ways to count, and one is far easier. The trick: count the easy side, then subtract from the total.

Contest counting hides this all the time. Whenever the thing you want is messy but its opposite is tidy, count the opposite and subtract.

This works because every item is either wanted or not — those two groups together are everything. So if you know how many total there are and how many are NOT wanted, the wanted count is the difference.

The classic signal: phrases like at least one, at least k, contains at least one X, has at least one event A. Trying to count these directly forces you into messy casework (“exactly 1, exactly 2, exactly 3, …”). Instead, count the complement (zero events) and subtract from the total.

Concrete example. How many 4-digit numbers contain at least one digit 2?

• Total 4-digit numbers: 9000 (from 1000 to 9999).
• How many contain no 2? The thousands digit has 8 choices (1, 3, 4, 5, 6, 7, 8, 9 — not 0, not 2). The other three digits each have 9 choices (any digit 0–9 except 2). Total without 2: 8 × 9 × 9 × 9 = 5832.
• So how many contain at least one 2? 9000 − 5832 = 3168.

Counting these directly would require casework on “exactly one 2 / exactly two 2s / exactly three 2s / four 2s” — many cases. Complementary counting collapsed it to one subtraction.

THE MOVE: when you see “at least one,” count the “none” case instead and subtract from the total.

When choices split into types and the counts are different in each type, count each type separately and add. This is called casework.

How to set up clean casework:

1. Pick the splitting criterion. (Often: “based on what the smallest item is” or “based on which of a few cases applies.”)
2. List the cases. They must be mutually exclusive (no overlap) and exhaustive (cover everything).
3. Count each case independently.
4. Add the counts.

The critical rules:

• If cases overlap, you'll double-count. Bad.
• If cases miss some items, you'll undercount. Also bad.

Concrete example. How many ways can two dice show a sum of 7?

Casework on the first die's value:

• First die = 1: second must be 6. (1 way)
• First die = 2: second must be 5. (1 way)
• First die = 3: second must be 4. (1 way)
• First die = 4: second must be 3. (1 way)
• First die = 5: second must be 2. (1 way)
• First die = 6: second must be 1. (1 way)

Total: 6 ways.

Casework on “first die value” gives mutually exclusive cases (first die can only be one number) and exhaustive (covers all 6 possibilities). Perfect.

Split on even vs. odd — the parity case

Some counting questions look like they need a giant sum-by-sum search. Often the only thing that matters is whether each number is even or odd. Split on that and the search collapses to two cases.

Why does parity do so much work? Because even/odd add in a fixed pattern, no matter the actual numbers:

• even + even = even
• odd + odd = even
• even + odd = odd

The rule for a sum: a sum is even exactly when it contains an even number of odd pieces (zero odds, two odds, four odds…). The evens never change the parity — only the odds flip it.

Concrete example. Pick 2 different numbers from {3, 7, 8, 10, 11}. How many pairs have an even sum? The set has 3 odds (3, 7, 11) and 2 evens (8, 10). A two-number sum is even only when both have the same parity:

• both odd: list the pairs of odds — {3,7}, {3,11}, {7,11} → 3 pairs.
• both even: only {8,10} → 1 pair.

Total 3 + 1 = 4 even-sum pairs — and you never added a single actual sum. You only counted odds and evens. (Counting pairs like this has a one-line formula, C(n, 2), waiting in chapter 8 — here the list is just as fast.)

Multiply WITHIN a case, add ACROSS cases

This is the line that ties chapters 2 and 4 together. Inside one case you make a chain of choices — that is an AND, so you multiply. Between separate cases you pick exactly one — that is an OR, so you add.

Picture a trip from town A to town D. You may go through B or through C, never both. From A there are 4 roads to B, then 3 roads from B to D; or 2 roads from A to C, then 5 roads from C to D.

Through B: 4 roads AND 3 roads → 4 × 3 = 12 trips. Through C: 2 AND 5 → 2 × 5 = 10 trips. The two routes are exclusive, so add: 12 + 10 = 22 trips. You multiplied inside each route and added across them — that is the whole grammar of counting in one picture.

Framing inspired by AoPS Prealgebra.

THE MOVE: split on the variable that gives the fewest cases — then count each and add.

Spin a spinner split into 4 equal wedges, one of them red. What is the chance of red? You did not reach for a formula — you said “1 out of 4” because one wedge out of four is red. That is the whole idea of probability, and you already own it.

Write it down: count the outcomes you want, count all the outcomes, divide. A probability question is really two counting questions wearing a disguise — which means every tool from the last four chapters works here too.

Probability of an event = favorable outcomes / total outcomes, when all outcomes are equally likely.

Watch it work — two-dice sum

Roll two dice. What’s the probability the sum is 7? Total outcomes: 6 × 6 = 36 (one for each (A, B) pair). Favorable: count the cells in the grid where the sum is 7.

Six cells light up — one for each pair (1,6), (2,5), (3,4), (4,3), (5,2), (6,1). So P(sum=7) = 6/36 = 1/6.

Four rules to KNOW COLD

Symmetry — count one side, the other matches

Two players each roll a die. What’s the probability the first roll is larger than the second? Your instinct is to march through all 36 cells and tally where first > second. Resist it.

Look at the two sides. “First larger” and “second larger” are mirror images — swap the two dice and one turns into the other. Nothing makes the first die special, so those two events must have the exact same probability. Symmetry hands you that for free.

So split the 36 outcomes into three buckets:

• tie (first = second): the 6 cells down the diagonal.
• first larger: some count.
• second larger: the SAME count, by symmetry.

The two “larger” buckets share what’s left after the ties: 36 − 6 = 30 cells, split evenly. So each is 30 ÷ 2 = 15. P(first larger) = 15/36 = 5/12. No cell-by-cell tally.

This is the same idea behind “count it once and multiply”: when a shape has matching halves — the 5 petals of a flower under rotation, the two ends of a necklace — you count one piece and use the symmetry instead of listing every case.

THE MOVE: a probability question is two counts — favorable on top, total on the bottom. Count both, then divide.

A bag has 5 red and 3 blue marbles. You pull two. After the first marble leaves your hand, here is the only question that matters: did the bag change? If you put the marble back, the bag is good as new and the second pull is a fresh 5-in-8. If you keep it, the bag shrank — now maybe 4 red in 7. That one difference is what makes a probability problem “independent” or “dependent.”

Two events are INDEPENDENT if the outcome of one doesn’t change the probability of the other:

• Flipping a coin twice — the first flip doesn’t affect the second.
• Rolling a die twice.
• Drawing a card and putting it back before drawing again.

Two events are DEPENDENT when one outcome affects the next:

• Drawing two cards WITHOUT replacement — the deck shrinks.
• Picking marbles without putting them back.

See the difference

The trap signal: read the words

THE MOVE: after the first pick, ask “did the pool change?” If yes, shrink the counts before the next step.

Exactly 2 heads — count the patterns, don’t list them

Flip a fair coin 3 times. What is the probability of exactly 2 heads? You could write out all 8 outcomes and tally. For 3 flips that is fine. For 10 flips it is a nightmare. There is a cleaner move that scales.

Step 1 — nail down ONE pattern. Take the specific sequence H H T. Each flip is independent, so multiply: ½ · ½ · ½ = 1/8. Any single 3-flip sequence has the same 1/8 chance — the coin does not care about order.

Step 2 — count how many patterns fit. “Exactly 2 heads” means choosing which 2 of the 3 flips are heads. Here you can just list them: HHT, HTH, THH — 3 patterns. (Chapter 8 names this “choose 2 of 3” count C(3, 2) and gives a formula for when the list gets long; for 3 flips the list is quickest.)

Step 3 — multiply. Each of the 3 patterns has chance 1/8, and they are mutually exclusive, so add them — which is the same as multiplying: 3 · 1/8 = 3/8.

This is why the casework never explodes: you price one arrangement, then let that “choose k of n” count handle the rest. With a fair coin every sequence is 1/2^n, so it collapses to C(n, k) / 2^n — and chapter 10 will show those counts are exactly Pascal’s triangle.

THE MOVE: price one pattern, then multiply by how many patterns there are.

Framing inspired by Competition Math for Middle School (AoPS) — price one arrangement, then multiply by the number of arrangements.

A room of 20 people: 15 drink coffee, 12 drink tea. Add those and you get 27 — more drinkers than there are people. Nobody cloned themselves. The 7 extra are the people who drink both, counted once in the coffee 15 and a second time in the tea 12. Add two overlapping groups and you always count the shared part twice.

So when two events can both happen, |A or B| is not |A| + |B| — that double-counts the overlap. Subtract the overlap once and the count comes back down to earth.

Picture it as a Venn diagram. Two overlapping circles. When you write |A| (the whole left circle), you've counted the overlap once. When you write |B| (the whole right circle), you've counted the overlap a second time. So |A| + |B| over-counts the overlap. Subtracting |A ∩ B| once fixes it.

Three sets. The pattern continues: add singletons, subtract overlaps, add the triple overlap back.

|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Where this shows up on contests:

• “X students play soccer, Y play basketball, Z play both — how many play at least one?” → |A| + |B| − |both|.
• “Numbers divisible by 2 or 3 in a range” → |mult of 2| + |mult of 3| − |mult of 6|.
• “Three overlapping shapes — how much total area?” → inclusion-exclusion on the shapes.

When no number fits one region — let the overlap BE the answer

Sometimes none of the given numbers belongs to a single region of the Venn diagram, so you cannot just write them in. The fix is a beautiful one: name the overlap with a letter — usually the very thing the problem asks for — write every region in terms of it, set the regions equal to the grand total, and solve.

Try it with a small zoo. A keeper has 27 animals: 14 are spotted, 11 are babies, and 5 are plain-coloured adults (not spotted, not babies). How many spotted babies are there? Nothing fits a single region yet, so let x = the spotted babies (the overlap, and the answer we want). Then the spotted-but-not-baby region is 14 − x, the baby-but-not-spotted region is 11 − x, and the 5 plain adults sit outside both circles.

Now add every region and set the sum to the total of 27:

(14 − x) + x + (11 − x) + 5 = 27

That collapses to 30 − x = 27, so x = 3. There are 3 spotted babies. (Check: spotted = 11 + 3 = 14 ✓, babies = 3 + 8 = 11 ✓, all four regions 11 + 3 + 8 + 5 = 27 ✓.)

Two habits make this reliable. Start from a region you actually know — often the middle overlap — and only reach for a variable when nothing fits. And if you feel stuck, look for the piece of given information you have not used yet; here it was the grand total of 27 that closed the equation.

A real contest case — ajhsme-1991-23: a band has 100 female and 80 male members; an orchestra has 80 female and 100 male; 60 females are in both; 230 students are in band or orchestra (or both). How many males are in band but not orchestra? First peel the genders apart. Distinct females = 100 + 80 − 60 = 120, so distinct males = 230 − 120 = 110. Now run the overlap-variable on the males: let x = males in both ensembles. Band-only males = 80 − x, orchestra-only males = 100 − x, and these three regions are all 110 males: (80 − x) + x + (100 − x) = 110, so 180 − x = 110 and x = 70. Band males who are not in orchestra = 80 − 70 = 10 — choice (A).

THE MOVE: add the groups, then subtract the overlap once — because adding both groups counted it twice.

Three runners cross the finish line. Now answer two different questions. “In how many orders can they finish?” — gold, silver, bronze all matter, so that is 6. “In how many ways can I pick 2 of them to interview?” — interviewing Ana then Ben is the same pair as Ben then Ana, so order does not matter, and that is only 3. Same three people, two different counts. The entire chapter rests on one question you ask every single time: does order matter?

If order matters, you are arranging — a permutation. If it does not, you are choosing — a combination. Here are the two formulas, but the question above is what tells you which to grab.

Permutations — watch the slots shrink

Ten sprinters race. You want gold, silver, bronze. Draw three empty slots and fill them left to right, asking the same question each time: who is still available?

That is all a permutation is — the multiplication principle with a pool that shrinks by one each step. P(n, k) means “start at n and multiply k shrinking factors”: P(5,3) = 5 · 4 · 3. Filling all the slots is the full factorial: P(5,5) = 5! = 120.

Combinations — the same picks, with order erased

Now interview 3 of 5 runners afterward — here order does not matter. Start from the 60 ordered picks you counted a moment ago, then group together the ones that are secretly the same trio. Take the three runners A, B, C. As an ordered pick they show up 3! = 6 different ways, but they are one and the same group:

Every group of 3 got counted 3! = 6 times in the ordered list. So to count groups, divide the ordered count by that overcount:

C(5, 3) = P(5, 3) ÷ 3! = 60 ÷ 6 = 10

Pictured-intuition adapted from Competition Math for Middle School (AoPS).

Factorial. n! (“n factorial”) = n × (n−1) × (n−2) × … × 2 × 1. So 5! = 120, 6! = 720, 7! = 5040. (Also 0! = 1 by convention.)

How to choose between permutations and combinations. Ask: does the order matter?

• “How many ways to seat 5 people in a row of 5 chairs?” Order matters → permutation. Answer: 5! = 120.
• “How many ways to choose 3 of 10 people for a team?” Order doesn't matter (Alice-Bob-Carol is the same team as Bob-Alice-Carol) → combination. Answer: C(10, 3) = 120.
• “How many ways to rank 3 winners (gold, silver, bronze) from 10 contestants?” Order matters (gold is different from silver) → permutation. Answer: P(10, 3) = 10·9·8 = 720.

The most-used combination. C(n, 2) = n(n−1)/2 is the number of pairs you can choose from n items — i.e., the number of handshakes among n people. For 5 people: 5·4/2 = 10 handshakes. For 10 people: 10·9/2 = 45. For 20 people: 20·19/2 = 190.

Why handshakes are n(n−1)/2 — see the double-count

Five friends, everyone shakes everyone once. Picture each person and draw a line to each of the others.

Each of the 5 people reaches out to 4 others — that is 5 × 4 = 20 reaches. But a handshake takes two people, and you counted it from both ends. Divide by 2: 20 ÷ 2 = 10. That is exactly C(5, 2) — choosing an unordered pair.

The same count is a stack of dots called a triangular number. The first person shakes 4 hands, the next adds 3 new ones, then 2, then 1: 4 + 3 + 2 + 1 = 10. Stacking those rows makes a triangle, and the count for n people is always 1 + 2 + … + (n−1) = n(n−1)/2. Handshakes, lines between dots, and games in a round-robin are all the same picture.

Pictured-intuition adapted from Competition Math for Middle School (AoPS).

Why 1 + 2 + … + n = n(n+1)/2 — the Gauss fold

The handshake count was 1 + 2 + … + (n−1) — a stack of rows. There is a one-move proof of the sum that a seven-year-old Gauss is said to have found. Write the sum forwards, write it again backwards underneath, and add the two columns:

Every column adds to the same n + 1, and there are n columns, so 2S = n(n+1) and

1 + 2 + … + n = n(n+1)/2.

So 1 + 2 + … + 100 = 100 × 101 / 2 = 5050 — no adding 100 numbers. And this is the twin of the handshake formula: n people make 1 + 2 + … + (n−1) = n(n−1)/2 handshakes (the same fold, one row shorter). Round-robin games, lines between dots, and the triangular numbers are all this one sum.

Diagonals of a polygon — and shaking all but a few hands

How many diagonals does a polygon with n sides have? A diagonal joins two corners that are not already next-door (those are edges, not diagonals). From any one corner you can reach the other n − 1 corners, but 2 of those are its neighbours — joined by edges — so only n − 3 of the reaches are diagonals. That is n × (n − 3) reaches over all corners, and each diagonal got counted from both of its ends, so halve it.

Check a pentagon: 5 × 2 / 2 = 5 diagonals. A hexagon: 6 × 3 / 2 = 9.

Shaking all but a few hands. The same “count everything, then take away the missing ones” move solves a classic. At a party of 7 married couples, everyone shakes hands once with everyone except their own spouse. How many handshakes? Pretend for a moment that everyone shakes everyone — that is 14 people, C(14, 2) = 14 × 13 / 2 = 91 handshakes. Now remove the ones that never happen: the 7 spouse-handshakes. So 91 − 7 = 84. Count the full thing, subtract the forbidden few — far easier than building the allowed handshakes one by one.

Framing inspired by AoPS Prealgebra.

Three more facts worth knowing by sight

Why? For each of the n elements, decide independently: in or out. That’s 2 choices, multiplied n times. A set of 3 items {A, B, C} has 2³ = 8 subsets: {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

So “how many subsets” questions never need a formula — it is 2 to the power of the count.

Why fewer than a row? Look at the same five friends arranged the same way, once in a row and once around a table:

In a row, each of the 5! = 120 shuffles is a brand-new arrangement — the chair you sit in matters. Around a table, only your neighbors matter. Rotating everyone one seat clockwise gives the “same” seating — you still see B on your left and E on your right. There are 5 rotations of every arrangement, so we divide: 120 ÷ 5 = 24.

Equivalent shortcut: fix one person in place (say A always at the top). Then arrange the other 4 in the remaining seats: 4! = 24. Same answer.

Example. 5 people round a table: 4! = 24. 6 people: 5! = 120. 8 people: 7! = 5040.

Let’s see why. Take a smaller word: BOOK (4 letters, but the two O’s are identical).

The MISSISSIPPI example

MISSISSIPPI has 11 letters: 1 M, 4 I’s, 4 S’s, 2 P’s.

For LEVEL (two E’s, two L’s): 5! / (2! · 2!) = 30. For LOOK (two O’s): 4! / 2! = 12. Same recipe every time.

Count the losers, not the games

A knockout chess tournament has 100 players. Lose once and you’re out. The last player standing is champion. How many games get played?

Your instinct is to add up the rounds: 50 games cut the field to 50, then 25, then … and now you’re stuck, because 50 isn’t even and the byes get fiddly. Resist that.

Look at it from the loser’s side instead. Every game has exactly one loser, and every loser is knocked out forever. At the end, 99 players have been knocked out (everyone except the champion). So exactly 99 losers happened — which means exactly 99 games. Done. No rounds, no byes, no powers of 2.

This works because you matched up two things one-to-one: each game ↔ the single player it eliminates. That kind of one-to-one match is the cleanest counting move there is. When a count looks tangled, ask: is there a thing I can pair each item with that’s easier to count?

(Careful: this is not the handshake count. Handshakes pair players with each other — that’s C(n, 2). Here you pair each game with its one loser — that’s n − 1. Read whether games happen between every pair, or only between survivors.)

Count the same total two ways — the handshake rule

Here is the slickest counting move of all: find one number that two different counts must both equal, and let them pin each other down. The classic is handshakes. Picture the party as dots with a line for each handshake; a person’s “handshake count” is how many lines touch their dot.

Add up everyone’s handshake count into one grand total. Each single handshake is a line with two ends, so it adds 1 to each of two people — it lands in the total exactly twice. So the same total has two readings: it is the sum of the counts, and it is also 2 × (number of handshakes). They must match.

One crisp payoff: the number of people who shook an odd number of hands is always even. Split the crowd into “even-counters” and “odd-counters.” The even-counters add to an even number; the whole total is even; so the odd-counters must add to an even number too — and a pile of odd numbers totals even only when there is an even number of them. That is why you can never have exactly 3 people who each shook an odd number of hands.

This is the same engine as the handshake formula and “count the losers”: instead of counting the thing asked, count a total that something else also measures, and read it from the easy side.

Strategy framing inspired by Posamentier, The Art of Problem Solving (teacher resource).

THE MOVE: ask “does order matter?” Order matters → permutation. Order does not → combination.

(Knockout-tournament idea adapted from Problem Solving via the AMC, Australian Maths Trust.)

You are at the bottom-left of a city grid and your friend is up and to the right. You only ever walk right or up — no backtracking. How many different routes can you take? You could try to draw them all, but there is a sneaky shortcut: every route is a sequence of moves, and you only have to decide the order of the rights and ups.

A lattice path is exactly this — a path on a grid using only fixed directions. The classic contest question: how many paths from one corner to another going only RIGHT or UP?

The clean observation

To get from (0,0) to (m, n), you ALWAYS need exactly m right-moves and n up-moves. The path is m+n moves total — you’re only choosing the ORDER.

Why combinations, not permutations?

The 3 R-moves are interchangeable — they all do the same thing. The 2 U-moves are also interchangeable. So we’re choosing POSITIONS for the R’s among 5 slots, not arranging 5 distinct items.

Path-through-a-point

“Paths from A to B that pass through P” — split into two legs.

Path AVOIDING a forbidden cell

Use complementary counting: (all paths) − (paths through forbidden cell). The second piece is itself a path-through-a-point count.

When the map isn’t a clean grid — label every corner

The C(m+n, m) formula only works on a perfect rectangle of streets. Real maps have a closed road, a one-way diagonal, a missing block. Then the formula breaks. There’s a method that never breaks.

Write a number at every corner: how many ways you can reach that corner from the start. The rule is dead simple — a corner’s number is the sum of the corners that feed into it (the one directly left, plus the one directly below, if you only move right and up). Start gets a 1. Then fill in, corner by corner, working away from the start.

Read the bottom row and left column: only one way to reach each (you can only walk straight, so each is 1). For every other corner, add the number on its left to the number below it. The corner immediately right of the closed road has nothing feeding it from the left — so it only gets its 1 from below, instead of the larger number it would have inherited. Keep adding left + below across the whole map. The END corner reads 9: nine safe routes.

On a fully open grid this same map would give C(4 + 2, 2) = 15 routes — but the closed road knocks it down to 9, and the labeling found that without any formula at all. A blocked road stops feeding its neighbor, and the count downstream drops on its own.

THE MOVE: a right/up path is a sequence of moves — count it as C(total moves, number of rights). On a broken map, label every corner and add.

(Add-into-each-vertex route-counting adapted from Problem Solving via the AMC, Australian Maths Trust.)

You have met C(n, k), lattice paths, and “exactly k heads” in different chapters. They are secretly the same numbers. There is one picture that holds all of them — a triangle of numbers you can build with nothing but addition.

Build it: each number is the sum of the two above

Start with a single 1 at the top. Every row starts and ends with 1. Every other number is the sum of the two numbers sitting above it — one to the upper-left, one to the upper-right. That is the whole rule. No formula, only adding.

The number you build is exactly C(n, k): go to row n, count k steps in from the left (starting at 0). Row 4 reads 1, 4, 6, 4, 1 — and sure enough C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1. So “6 ways to pick 2 of 4” is the middle of row 4.

Why each is the sum of the two above

Look at C(4, 2) — choosing 2 things from {A, B, C, D}. Stare at one item, say D. Either D is in your pick or it is not.

• D is in: you still need 1 more from {A, B, C} — that is C(3, 1) = 3 ways.
• D is out: you need all 2 from {A, B, C} — that is C(3, 2) = 3 ways.

Add the two cases: 3 + 3 = 6 = C(4, 2). Those two pieces, C(3,1) and C(3,2), are exactly the two numbers in the row above. That is why you add the two above — it is the “is this one item in or out?” split, drawn as a triangle.

Each row adds up to a power of 2

Add across any row: 1, then 1+1=2, then 1+2+1=4, then 1+3+3+1=8, then 16, then 32… The totals double every row: row n sums to 2n.

This is the subset count from chapter 8 in disguise. Flip n coins and C(n,k) counts the outcomes with exactly k heads; add the whole row and you get every outcome, 2n. So “exactly 2 heads in 4 flips” is the 6 in row 4, out of the 16 total — 6/16.

It is also the lattice-path grid, tilted

Remember labeling each corner of a grid with “how many ways to reach it” — each corner was the sum of the one left and the one below? Tilt that grid 45° and it is Pascal's triangle. The path counts and the triangle entries are the same numbers.

THE MOVE: when a count smells like “choose k of n,” build Pascal’s triangle by adding, and read off row n, position k.

Pictured-intuition adapted from Competition Math for Middle School (AoPS).

Imagine 10 pigeons and 9 nesting boxes. No matter how the pigeons choose, some box must contain at least 2 pigeons. That's the pigeonhole principle.

The principle sounds obvious, but it's a precision tool. It lets you prove that something must exist without finding it explicitly — perfect for 'least number to guarantee' problems.

The contrapositive view (what these contests actually ask). 'Least number to guarantee N of the same kind.' Imagine the worst case: an adversary who spreads things as evenly as possible. How many more do you need to force a clump of N?

If you have k colors and want to guarantee N of one color, the worst case has N − 1 of each color before you finish — that's k(N − 1) items. The next item (one more) must complete a group of N.

Walkthrough. A drawer has socks in 3 colors. How many socks must you pull (worst case, in the dark) to guarantee a matching pair?

• k = 3 colors, N = 2 (matching = pair).
• Formula: 3·(2−1) + 1 = 4 socks.
• Worst case: first 3 socks could all be different colors. The 4th must match one of them.

The same logic scales up: 9 colors, want 4 of one → 9·3 + 1 = 28 items.

THE MOVE: for “guarantee,” imagine the unluckiest spread, then add one to force the clump.

Here’s a classic question that shows up a lot: you have 7 identical cookies to share among 3 kids. How many ways are there?

The kids don’t have to get the same number. One kid could even get zero. As long as the totals add up to 7, it counts as a valid sharing.

This sounds hard. There’s a beautiful picture-based trick that makes it easy.

The picture: stars and bars

Draw the 7 cookies in a row as stars. To split them among 3 kids, you need 2 dividers (called bars) between the stars. The cookies before the first bar go to kid 1, the cookies between the two bars go to kid 2, and the cookies after the second bar go to kid 3.

Every way of arranging 7 stars and 2 bars in a row corresponds to exactly one way of sharing the cookies. So now you count arrangements of 7 stars and 2 bars.

Counting the arrangements

There are 7 + 2 = 9 positions in the row. We pick which 2 positions are bars; the rest are stars. From chapter 8, that's C(9, 2) = 9 · 8 / 2 = 36 ways.

So there are 36 ways to share 7 cookies among 3 kids (zeros allowed).

The “each kid gets at least one” trick

Often the problem says every kid must get at least one cookie. The trick: give every kid one cookie up front, then share what’s left freely.

Example. 7 cookies, 3 kids, each kid at least 1. Hand out 3 cookies up front (one per kid). Now share the remaining 4 cookies among the 3 kids with no minimum. That’s C(4 + 2, 2) = C(6, 2) = 15 ways.

THE MOVE: identical items, distinct people → draw stars and (people − 1) bars, then count where the bars go.

The same trick counts dice sums

Here is a place the dividers sneak in where you would not expect them. In how many ways can three dice show a sum of 6? (Order matters — a red 1, white 2, blue 3 is different from 3, 2, 1.)

Your instinct is to hunt for triples that add to 6 and count the orderings of each. That works, but it is fiddly. Here is the divider view. Draw the 6 as 6 dots in a row. Slot 2 dividers into the gaps to cut the dots into three piles — the first pile is die 1, the middle is die 2, the last is die 3:

Two rules make this match the dice exactly. Every die must show at least 1, so no divider can sit at either end (that would give a pile of 0). And two dividers cannot share the same gap, so no two dividers are adjacent. Six dots leave 5 inner gaps, and you drop 2 dividers into different gaps: C(5, 2) = 10 ways.

So three dice make a sum of 6 in 10 ways. (Sanity check by listing the triples: 1-1-4 has 3 orderings, 1-2-3 has 6, 2-2-2 has 1 — that is 3 + 6 + 1 = 10. The dividers got there without the case-hunt.) The gap rule “no end, no doubling up” is exactly the “each person gets at least one” trick wearing a costume — every die is a person who must get at least 1 pip.

Framing inspired by Competition Math for Middle School (AoPS) — the “Sticks and Stones” divider model, including the dice-sum variant.

“How many rectangles are in this picture?” feels like a spot-and-count chore where you point at each one and hope you did not miss any. There is a far safer way: instead of hunting for the figures, count the choices that build them. Each figure is pinned down by picking a few key pieces — count the ways to pick, and you have counted the figures, with nothing missed and nothing doubled.

Here is the key idea for rectangles: every rectangle is fixed by two vertical lines and two horizontal lines. Pick the two lefts/rights, pick the two tops/bottoms — you have named exactly one rectangle.

So counting rectangles = counting ways to choose 2 lines from each direction:

A grid that is 3 squares wide and 2 tall has 4 vertical lines and 3 horizontal lines, so it holds C(4,2)×C(3,2) = 6×3 = 18 rectangles.