02The Art of Counting

At the end of the last chapter we walked straight into a wall. We had found that probability is favourable outcomes over total. List them, count them, divide. That worked beautifully for one coin, for two coins, for a pair of dice. Then we asked about a hundred flips. That sample space holds 2¹⁰⁰ outcomes, which is about 1.27 × 10³⁰ of them. A machine listing a billion a second would still be writing 40 trillion years from now. That single run is 2,900 times the age of the universe. It's a list no human and no machine will ever write down. The method was right. The brute enumeration was hopeless. So this whole chapter builds the thing that rescues it: a counting engine that counts the favourable outcomes without ever listing them. And here's the surprise most courses bury on their way to the formulas. The entire engine turns on just two yes/no questions you ask of any counting problem: does order matter, and can things repeat? Answer those two and the right formula is already chosen for you. We'll build all four of them from nothing. We'll uncover why a combination divides by r!, stack the answers into Pascal's triangle, and watch the bell curve wave back at us from the far end of the course. Only then do we divide. Counting was never the same thing as probability, and the dividing is the trivial last step. No magic in any of it — just careful counting of a world too big to watch all at once.

01The two switches

Let's meet the wall head-on, then find the door in it. Counting by hand is a list: write out every possibility, then count the ones you want. That's exactly what we did for two dice, and it was fine, because 36 cells fit on a page. But the list explodes the instant a problem gets real. Pick a 4-digit PIN and there are ten thousand of them (10 × 10 × 10 × 10). Deal a 5-card poker hand and there are over two and a half million (2,598,960 of them exactly). Nobody lists those. What we need is a way to know how many there are without producing them one by one. The first step is noticing that not all counting problems have the same shape. Take one concrete task below — choosing a few letters from a small set — and flip the two switches on it. Watch the valid possibilities re-sort themselves before your eyes.

Feel what just happened: the same words — "pick some letters" — meant four completely different counts, and only two questions decided which. Does the order of your picks matter, so that AB counts as different from BA? And can you repeat a pick, so that AA is allowed? Those two yes/no switches, and nothing else, split every counting problem in the book into one of four kinds. So before you reach for any formula, you ask the two questions. That habit is the whole art.

Which means the entire chapter fits inside a single picture: a 2×2 grid. Order runs down one side, replacement runs across the other, and a formula lives in each of the four boxes. This is the map we're about to fill in. Toggle the two switches and watch the lit box swap in real time, along with its formula and a running worked example. Don't worry about why each formula is what it is yet. Right now just see that there are exactly four boxes, and that two switches select among them.

Here is the trap almost every beginner walks into: order mattering is never a fact about the objects. The very same three runners are ordered when you hand out gold, silver and bronze. Those same three runners are unordered when you only pick who makes the final. The question decides, not the things. The grid picks the formula once you set the two switches, but the real skill is the step before that: reading a plain-English problem and setting the switches yourself. So try it before you trust it.

There it is: the whole lecture compressed into one control. Ordered, repeats allowed gives nʳ. Ordered, no repeats gives n!/(n−r)!. Unordered, no repeats gives the famous C(n,r). And the fourth box, unordered, repeats allowed, has a formula almost every course forgets: C(n+r−1, r), which we'll earn together. The rest of this section walks into each box and builds its formula from the ground up, so you never have to memorize one again.

02The four boxes

Start with the friendliest box: order matters and repeats are allowed. Picture a 3-wheel combination lock, each wheel showing the digits 0–9. The first wheel gives you 10 choices. Whatever you pick there, the second wheel still offers all 10. The pool never shrinks, because the wheels don't know or care about each other. They're independent, and independent choices multiply. Turn the wheels below and watch the total climb to a thousand settings, as 10 × 10 × 10.

The wheels multiplied because every slot offered the same 10 options no matter what the other wheels showed. That independence is the whole license to multiply, and it can fail. Multiplication needs one thing: every step must offer the same count of options, whatever you picked before. The moment a later choice depends on an earlier one, the branches stop being equal and a flat product quietly lies. Watch a tree where every node has the same number of children. Then watch one where it doesn't.

That's the first formula, and it's the cleanest. You have r slots and n options at each slot, with the pool held constant, so the count is n × n × … × n = nʳ. This single expression is why brute force explodes. An 8-character password drawn from a 94-symbol keyboard has 94⁸ possibilities, about six quadrillion of them. That same "vocabulary-to-the-length" shape drives every cracking-time estimate, every DNA-codon count, and every tensor you’ll ever multiply out. When the pool doesn't shrink, counting is just repeated multiplication.

Now flip one switch. Keep order mattering, but forbid repeats. This is dealing cards. The first card can be any of 52. But once that card is out of the deck, the second card can only be one of the 51 that remain, then 50, then 49, then 48. The pool depletes by one on every draw. Deal below and watch the shrinking pool sit beside the constant pool from the lock. That is the difference between the two boxes, made visible.

So five ordered cards come to just over 311 million deals: 52 · 51 · 50 · 49 · 48, a descending run with one option fewer at each step. Write that descending run as a ratio of factorials and it becomes the box's formula: n!/(n−r)!, the number of permutations of r things drawn from n. (That descending product is easy to slip on. Count the factors, one per card dealt, and it stays honest.) The whole difference from the lock is a single word. Drawing without replacement means the pool remembers what you've taken.

That n! sitting in the formula deserves a proper introduction, because it's the engine under everything that follows. n factorial is just the number of ways to arrange n distinct things in a row: n choices for the first spot, n−1 choices for the next, all the way down to 1. Ten books on a shelf arrange in three and a half million orders (10! = 3,628,800). Step it down below, and watch what happens when you reach the very bottom, at 0!.

Here's the part that trips people: 0! = 1. It looks like a rule invented to make formulas behave, but it isn't. It's a count, and it's honest. How many ways are there to arrange nothing? Exactly one way: the empty arrangement. Do nothing, and you have done it the single way it can be done. So 0! = 1 is not a convention pulled from a hat. It's the true answer to a real question, and it is why the permutation formula still works when you take everything or take nothing.

Now the box the whole chapter pivots on. Flip the last switch: order no longer matters. A 5-card poker hand is the same hand however you sort it. The ace-high straight is one hand, not the 120 different orders you could have dealt it in (5! = 120). But our permutation count did treat all 120 of those orders as separate hands. So the permutation count over-counted, and it over-counted by an exact, knowable amount. Take one fixed selection below, fan it into every order it could appear in, then collapse those orders back to the single unordered pick.

Fig. 8 fanned one team into its 6 orderings. But dividing by r! is only honest if every team gets the same 6 orderings, no more and no less. It does, and here is why you can trust it. The figure's case is a team of three chosen from five people, so r = 3 and r! = 3! = 6. Line up all 60 ordered picks, which is 5 × 4 × 3, and they fall into tidy columns — one column per unordered team, each column exactly 6 tall. Sixty picks in columns of six leaves 10 columns, so 10 teams. The ordered pile is a perfect rectangle: teams across, orderings down. Dividing by r! is just reading off how many columns there are. Sort them yourself and watch no column ever come up short.

This is the keystone of the entire chapter, so let's say it slowly. Every unordered selection of r things shows up exactly r! times among the ordered ones, once for each way of shuffling those same r things. So the ordered count is r! times too big. To fix it, you divide by r!. That's the whole repair. And that division isn't a step toward the combination. That division is the combination. Understand this one move and you never memorize C(n,r) again; you reconstruct it.

Put the pieces together and the famous formula assembles itself. Order-with-depletion gave n!/(n−r)!. Correcting the over-count means dividing by r!. Do both and you have the combination, C(n,r) = n! / (r!(n−r)!), read out loud as "n choose r." Run poker through it and 311 million ordered deals collapse to two and a half million hands (C(52,5) = 2,598,960). Every one of those three factorials has a job. Explore it below: each factor lights up with the exact role it plays.

Look again at fig. 7: r! and (n−r)! sit in the formula doing mirror-image jobs, and that symmetry is a free gift hiding in plain sight. Every time you choose r things to keep, you have in the same breath chosen the n−r things to throw away. Pick either side and the other side is already decided. The two choices are one act seen from two angles. So C(n,r) = C(n,n−r), exactly, and a monster like C(52,50) is really the baby C(52,2) in disguise — a mere 1,326 pairs. Flip between keep and toss and watch the count refuse to move.

So n! arranges everything, (n−r)! cancels the arrangements of the things you didn't pick, and r! cancels the arrangements of the things you did. What is left is a clean count of selections in which order is irrelevant. Three of the four boxes are now built from nothing but multiplication and one division. The fourth box is the sneaky one.

Back to order doesn't matter, but now repeats are allowed. This is the box most textbooks skip. Think of buying r scoops of ice cream from n flavours. You can double up on chocolate, and "chocolate then vanilla" is the same cup as "vanilla then chocolate." The trick that cracks it is a change of picture called stars and bars. Lay your r scoops out as stars, then separate the flavours with n−1 bars. Every arrangement of stars and bars is exactly one valid selection. Click a divider, then click where it should land, and watch each layout become one selection.

Count the arrangements and the fourth box falls out. You have r stars and n−1 bars, which is n+r−1 symbols in a row, and all you do is choose which positions hold stars: C(n+r−1, r). Three scoops from five flavours is 35 different cups by that count (C(7,3) = 35). That's the cell almost nobody teaches. Now the grid is complete: two switches, four boxes, four formulas, every one of them derived rather than memorized. Everything else in counting is these four wearing costumes.

03Pascal's triangle

The combination numbers C(n,r) aren't a scattered pile. They lock together into one of the most beautiful objects in mathematics. Write C(0,0) at the top, which is 1, then let each row below it hold the choices for the next n. A pattern jumps straight out: every interior number is the sum of the two directly above it. Build the triangle below, and click any cell to see its two parents light up and add to it.

That "sum of the two above" isn't a coincidence to marvel at. It has a reason you can hold in your hand. Ask C(n,r) its own question: how many ways are there to choose r things from n? Single out one specific element, say the newest person added to the group. Either that person is in your selection, in which case you choose the remaining r−1 from the other n−1 people: that's C(n−1,r−1). Or that person is out, and you choose all r from the other n−1: that's C(n−1,r). Every selection is one or the other, and never both. Step through that split below.

So the addition rule C(n,r) = C(n−1,r−1) + C(n−1,r) is just "the new element is in, or it's out" written in symbols. The whole triangle is that one honest choice, repeated row after row. Which makes Pascal's triangle not a curiosity but a machine: you can generate every combination number with nothing but addition, and no factorials at all.

And now the payoff that reaches across the entire course. Look at a single row of the triangle as a bar chart: small at the ends, fat in the middle. Row 4 reads 1, 4, 6, 4, 1, and the hump is already there. That's the shape of the binomial coefficients. As n grows, the shape sharpens into something you already half-recognize. Slide n up and watch the row of coefficients settle, once normalized, onto a smooth bell.

That bell is the normal distribution. It shows up here out of pure counting, before we have said a word about randomness, and that is the Central Limit Theorem waving at us from the far end of the book. Hold onto the sight; we'll come back and prove it. For now, just register the wonder. The same numbers that count poker hands, stacked high enough, are the curve that governs measurement error, exam scores, and the drift of the stock market. Counting and the bell are the same story told at two scales.

04More than two kinds

So far every selection sorted things into two piles: chosen or not, in or out. But plenty of problems have more than two categories. How many distinct ways can you arrange the letters of MISSISSIPPI? Eleven letters go in, but they arrive as 4 S's, 4 I's, 2 P's and 1 M, and swapping two identical S's changes nothing. It's the over-count problem again, now running on several fronts at once. Rearrange the tiles below and watch the identical-letter swaps collapse to the same word.

The fix is the same move fired repeatedly. Start with all 11! arrangements, as if every letter were distinct, which is just under forty million of them (11! = 39,916,800). Then divide away the arrangements you can't tell apart: 4! for the S's, 4! for the I's, 2! for the P's. That gives the multinomial coefficient 11! / (4! · 4! · 2! · 1!), which comes out at 34,650 distinct words. And here's the lovely part. This isn't a new formula to bolt on. It telescopes out of the C(n,r) you already own. Choose which positions the S's take, then the I's from what's left, then the P's — a product of combinations — and watch the factorials cancel down the chain.

Each combination in that chain cancels neatly into the next, telescoping down to a single clean quotient: n! / (n₁! n₂! … n_k!). The binomial coefficient is just that same quotient with two groups, chosen and unchosen. So the multinomial isn't a cousin of the combination. The multinomial is the same idea generalized from two piles to many. And that clears up a naming trap worth stating plainly, because it is exactly where courses — including the one behind this book — tangle their terms.

Four laws sit close enough to be confused, and two questions tell them apart: do you put each pick back? and how many categories are there? With replacement and two categories you get the binomial. With replacement and more than two categories you get the multinomial. Take replacement away and two categories give the hypergeometric, while more than two give its cousin, the multivariate hypergeometric. Sampling a deck without putting cards back is not multinomial. It's hypergeometric, and mixing those two up is a genuine error we're going to get right. Here they are, sorted by the two questions in one card.

Fig. 18 lights the right cell once you set the two toggles. The skill that survives the exam is doing it the other way round: hearing a sampling story and setting the toggles yourself. This is exactly where courses slip. A deck dealt without replacement feels like it has many card-types, so people reach for the multinomial, when the honest answer is hypergeometric. Two questions save you every time: do you put each pick back, and how many categories are there? Read each story below, call the law before the reveal, and let the card catch you when you slip.

Keep that card in your head. It turns four intimidating names into four cells of a small table. And notice the deepest thread running under all four: every one of them is powered by the same over-count correction you learned in the poker box. Now let's build the one law we've only named so far, the honest count of a shrinking pool.

05When the pool shrinks

Here's where the two-category-with-replacement math quietly breaks. Suppose an urn holds 4 red balls and 4 blue ones, eight in all, and you draw a handful. If you draw with replacement — peek, then put the ball back — the chance of red stays a flat 1/2 on every single draw, and the count is a plain product. But draw without replacement and every ball you pull changes the odds for the next one. Pull one red out and red's chance drops to 3/7. Draw a few below with the switch flipped each way, and watch the probability of red hold steady, or drift.

That drift is the whole reason we need a separate law. When the pool depletes, you can't pretend each draw is a fresh independent coin. The draws are coupled. To count honestly, we go back to combinations. Say the urn holds k red balls among n in total, and you scoop out r of them. The chance of getting exactly m red is then a ratio of pure counts. Set the urn and the scoop below and watch that count assemble.

Read the formula as three counts stacked. There are C(k,m) ways to choose your reds from the reds, times C(n−k, r−m) ways to choose the rest from the blues, all sitting over the C(n,r) ways to choose the scoop from the whole urn. That's the hypergeometric distribution. Notice that we are already dividing counts to get a probability, which is the tell that we've quietly crossed a line. Counting was the hard part. The division was trivial. And that's the point this chapter has been walking toward.

06You are here

Step back and see what we actually did. Every probability in this chapter came out the same way: count the favourable outcomes, count the total, divide. The counting was the entire job — permutations, combinations, stars and bars, telescoping multinomials. The dividing was one keystroke at the end. That is worth making explicit, because it's easy to think probability is doing the heavy lifting when combinatorics is doing all of it. Watch a real probability assemble from its two counts below.

So counting and probability are decoupled: master the count and the probability comes free. That is exactly why we spent a whole chapter here before returning to chance. The counting engine you just built is the muscle behind half the results still ahead of us. Let's put it on the map.

There's our rung, lit: the counting engine, sitting one step above Chapter 1's favourable fraction. It is still just smarter counting of that same ratio. Everything above it on the tree — measures, conditioning, the Bayes flip, the whole family of distributions — leans on the counting you now own. But before we climb, there's a crack in the floor we have to look at.

Everything we counted, we counted as if every outcome carried equal weight. That's the same quiet assumption from Chapter 1, still load-bearing and still unmentioned. Our formulas count possibilities, and turning a count into a probability by dividing only works when those possibilities are equally likely. Bias one coin and the counts don't change at all, not by a single unit. The probabilities do. Watch the count sit frozen while the true chances peel away.

So here's the next honest wall. Counting is a magnificent engine, but it hands us probabilities only in the fair, equally-likely world. The moment weight is uneven — a loaded die, a biased coin, a continuous spin — "count and divide" is no longer enough. We need to stop counting outcomes and start measuring them: assigning weight directly to events, to whole regions of the sample space. That upgrade, from a count to a measure, is the language the next chapter teaches. And now you can feel exactly why we need it.