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

The most underrated tool in counting is just writing them all out. For small problems (fewer than ~20 items), listing is faster, less error-prone, and more reliable than any formula.

How to list cleanly:

1. Pick an order — alphabetical, smallest-first, lexicographic, whatever's natural.
2. Write items in that order, never skipping.
3. Cross off duplicates as you find them.

The pitfall isn't that listing takes too long — it's that students list randomly and either miss items or count duplicates. Always pick a definite order before you start.

Tiny example. How many ways can you arrange three letters A, B, C in a line?

List in alphabetical-first order:

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

That's 6 arrangements. Notice the order: start with A as first letter (then BC or CB), then B as first (AC or CA), then C as first (AB or BA). Always systematic.

(This pattern is also 3! = 3 × 2 × 1 = 6, which we'll see in chapter 8. But for small numbers, listing is clearer.)

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).

Sometimes the question asks for the count of something messy ("at least one of X happens"), but counting the opposite is much cleaner. Then you 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.

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.

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

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

What if two events can both happen? Then |A or B| isn't just |A| + |B| — that double-counts the overlap. You have to subtract the overlap once.

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 AMC:

• "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.

Two classical formulas for counting arrangements:

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.

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 — just 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.

A lattice path is a path on a grid that only uses fixed directions. The classic AMC question: how many paths from one corner of a grid 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 just 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.

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 AMC actually asks). '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.

This is a classic kindergarten-level pigeonhole. The same logic scales up: 9 colors, want 4 of one → 9·3 + 1 = 28 items.

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 we just 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.

“How many rectangles (or squares, or triangles) are in this figure?” looks like a spot-and-count chore. On a clean grid it's actually a choose problem in disguise.

Here's the key idea: every rectangle is fixed by two vertical lines and two horizontal lines. Pick the two lefts/rights, pick the two tops/bottoms — you've 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.