Somewhere near you, perhaps in a desk drawer or a fire safe, there may be a small card with twelve ordinary English words written on it in careful handwriting. Whoever holds that card holds the money. There is no bank to call, no password to reset, no manager to vouch for you — the words are the vault door, and the card is the only key.
How safe is that card? Stripped of everything else, the question is this: if a thief set out to guess the words, how many combinations would they have to work through? That is not a question about cryptography, or computers, or anything you need a degree for. It is a question about counting — and counting is something you already know how to do.
This chapter does that counting carefully, and the card never leaves the table. By the end you will have counted the twelve-word phrases yourself, three different ways, and the exact numbers will be printed where you can check them. To get there you will pick up the three tools that answer every counting question in this book: choices that multiply, a ladder that doubles, and the difference between order mattering and order not mattering.
First, pin the question down, because a vague question gets a vague answer. The twelve words on the card are not just any words. They come from a standard, public list of exactly 2,048 English words, and they are written down in order. (You will meet the list itself, and the standard behind it, in Chapter 11. For now, all that matters is its size: 2,048 words.)
So the safety question becomes three honest counting questions, and they have three different answers:
Each of these is a precise question with an exact whole number for an answer, and by §1.6 you will have all three. But you cannot jump straight at them, because nobody can multiply twelve 2,048s in their head without a method. The method is the next three sections: a rule about multiplying, a ladder of doublings, and a way to handle order. Then the card gets counted.
Start smaller than a vault. Start with a closet. You own 3 shirts and 4 pairs of pants, and an outfit is one of each. How many outfits are there?
You could list them: the blue shirt with the first pair of pants, the blue shirt with the second, and so on — four outfits for the blue shirt, four for the gray shirt, four for the white one. Three shirts, each paired with all four pairs of pants, gives \(3 \times 4 = 12\) outfits. Notice what did not happen: the choices did not add. There are not \(3 + 4 = 7\) outfits. Each shirt is a complete set of four pant-choices, so the pants get counted once per shirt — three groups of four. Add a third stage, say 2 jackets, and every one of the 12 shirt-and-pant combinations pairs with both jackets: \(12 \times 2 = 24\). Each new stage multiplies the running total by its number of options. That is the whole rule, and it is worth stating properly:
If a choice is made in stages, one after another, and the first stage has some number of options, the second stage has some number of options, and so on — and what you pick at one stage does not change what is available at the next — then the total number of outcomes is the numbers of options multiplied together. Write the option-counts side by side and multiply.
Now the vault's little cousin: the 4-digit bank card PIN. A PIN is four stages — first digit, second digit, third, fourth — and each stage has 10 options, the digits 0 through 9. By the multiplication principle there are \(10 \times 10 \times 10 \times 10 = 10{,}000\) possible PINs. Four tens multiplied together comes up so often it gets a shorthand: \(10^4\), read "ten to the fourth," means four tens multiplied. (In that notation, the little number up top just counts how many copies of the base are being multiplied: \(10^4\) is \(10 \times 10 \times 10 \times 10\).)
Is 10,000 a lot? Compare it to the 6-digit version some banks now use: \(10^6 = 10 \times 10 \times 10 \times 10 \times 10 \times 10 = 1{,}000{,}000\). Going from four digits to six multiplies the count by \(10^6 / 10^4 = 100\) — a hundred times as many codes for a thief to try. Two extra digits did not add two units of safety; they multiplied the space by a hundred. That is the first thing to feel about counting: more stages multiply, and multiplying is strong.
A state issues plates with three letters followed by three digits (ABC 123). Letters give 26 options per stage, digits give 10, so the multiplication principle gives
possible plates — about seventeen and a half million. When a state runs out, it does not invent longer plates by adding one more option; it adds one more character, one more stage, and the whole space multiplies by 26 or 10 again.
One kind of stage matters more to this book than any other: the stage with exactly two options. A coin flip. Heads or tails, nothing else. Count the outcomes as flips are added:
Every extra flip doubles the count. That is just the multiplication principle with 2 options at every stage: \(n\) flips give \(2 \times 2 \times \cdots \times 2\), with \(n\) twos, which we write \(2^n\) and read "two to the \(n\)." Here is the ladder, climbed twenty rungs — every entry computed, none estimated:
| \(n\) | \(2^n\) | \(n\) | \(2^n\) |
|---|---|---|---|
| 1 | 2 | 11 | 2,048 |
| 2 | 4 | 12 | 4,096 |
| 3 | 8 | 13 | 8,192 |
| 4 | 16 | 14 | 16,384 |
| 5 | 32 | 15 | 32,768 |
| 6 | 64 | 16 | 65,536 |
| 7 | 128 | 17 | 131,072 |
| 8 | 256 | 18 | 262,144 |
| 9 | 512 | 19 | 524,288 |
| 10 | 1,024 | 20 | 1,048,576 |
Two rungs are worth knowing by heart. \(2^{10} = 1{,}024\) — a shade over a thousand, close enough that "about a thousand" is an honest approximation. And \(2^{20} = 1{,}048{,}576\), about a million with change. Notice the eleventh rung: \(2^{11} = 2{,}048\). The wordlist from §1.1 has exactly 2,048 words, which means one word from the list carries exactly as much choice as eleven coin flips. Hold that fact; §1.6 spends it.
Since \(2^{10}\) is about a thousand, every ten extra flips multiply the count by about a thousand. Ten flips, a thousand. Twenty flips, a million. Forty flips, a shade over a trillion. You run out of names for the numbers long before the ladder runs out of rungs. A Bitcoin key lives at 256 flips — what that height means is Chapter 7's question, and this ladder is the way there.
A single two-option stage has a name in computing: a bit — one coin flip's worth of choice, written 0 or 1. Eight bits make a byte, and the ladder tells you a byte holds \(2^8 = 256\) different values. Nothing in this chapter needs more than that: a bit is one flip, and flips double.
Back to the closet, then to the bookshelf. You have 3 paperbacks — call them \(A\), \(B\), and \(C\) — and you are arranging them left to right on a shelf. How many arrangements are there?
Use the multiplication principle, but watch what happens to the stage sizes. Leftmost slot: 3 choices, any of the books. Middle slot: only 2 choices remain, because one book is already shelved. Last slot: 1 book left. The total is \(3 \times 2 \times 1 = 6\) arrangements — and you can check by listing: ABC, ACB, BAC, BCA, CAB, CBA. Six, as promised.
The stages shrank as books were used up, because arranging does not allow repeats: once \(A\) is shelved it cannot be shelved again. Arrangements of all \(n\) distinct things therefore come to \(n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\), a product that gets its own name and its own punctuation:
For a whole number \(n\), the product of all whole numbers from \(n\) down to 1 is written \(n!\) and read "\(n\) factorial":
\[ n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1. \]It counts the ways to arrange \(n\) distinct things in a row. So \(3! = 6\), and twelve distinct books can be shelved in \(12! = 479{,}001{,}600\) ways — nearly half a billion arrangements of one little shelf.
The \(n!\) notation is younger than the United States: the French mathematician Christian Kramp introduced it in 1808, in a textbook on arithmetic. It caught on because the product it names comes up constantly — every time order matters and nothing may repeat, a factorial is somewhere nearby.
One refinement, and then the shelf is fully understood. What if you arrange only some of the books — say 3 books chosen from 5, in order? The same shrinking-stages argument gives \(5 \times 4 \times 3 = 60\): three stages, starting at 5. In general, ordered arrangements of \(k\) things drawn from \(n\) distinct things come to a falling product of \(k\) factors starting from \(n\):
\[ n \times (n-1) \times \cdots \times (n-k+1) \;=\; \frac{n!}{(n-k)!}. \]The fraction form is worth one slow look: \(n!\) arranges all \(n\) things, and dividing by \((n-k)!\) cancels the arrangements of the \(n-k\) things you left behind. You will use this on the card in §1.6, where \(n = 2{,}048\) and \(k = 12\).
Now change the question one more time. Five friends — Ann, Bo, Cy, Di, Ed — and you need a team of 2 for a three-legged race. How many teams are there?
Start with what you know: ordered picks of 2 from 5 are a falling product, \(5 \times 4 = 20\). But a team has no order. Ann-then-Bo and Bo-then-Ann are the same team wearing different name tags, and in the count of 20 that team was counted twice — once for each of its \(2! = 2\) internal arrangements. Every team was counted twice. So divide the duplicates out: \(20 / 2 = 10\) teams. (Check by listing: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. Ten.)
That is the whole move: count as if order mattered, then divide by the arrangements of each unordered group. Stated generally it earns its own name and notation:
The number of ways to choose \(k\) things from \(n\) distinct things, when order does not matter, is the falling product of \(k\) factors from \(n\), divided by the \(k!\) arrangements of each chosen group:
\[ \binom{n}{k} \;=\; \frac{n \times (n-1) \times \cdots \times (n-k+1)}{k!} \;=\; \frac{n!}{k!\,(n-k)!}. \]The tall-parenthesis symbol is read "\(n\) choose \(k\)." So 2 from 5 is \(\binom{5}{2} = 10\), and 2 from 10 is \(\binom{10}{2} = 45\).
One special case does heavy lifting later in this book. Choosing two from \(n\) — counting pairs — is \(\binom{n}{2} = \frac{n(n-1)}{2}\): \(n\) choices for the first member, \(n-1\) for the second, divided by 2 because a pair has no first and second. Keep the formula; nothing more about pairs is needed yet.
Every tool is now on the table. Back to the card. Three questions from §1.1, three counts — each one exact, each one checkable on your own machine at the end of this section.
First question: any words, repeats allowed, order mattering. Twelve stages, each with 2,048 options, nothing used up:
\[ \underbrace{2{,}048 \times 2{,}048 \times \cdots \times 2{,}048}_{\text{twelve copies}} = 2{,}048^{12}. \]Here the ladder pays its dividend. The wordlist has \(2{,}048 = 2^{11}\) words, so each word is eleven twos multiplied; twelve words is twelve groups of eleven twos, which is \(12 \times 11 = 132\) twos all told:
\[ 2{,}048^{12} = 2^{132}. \]2048^12 = 2^132 =5,444,517,870,735,015,415,413,993,718,908,291,383,296
That number is forty digits long. Written out with all its digits it does not look like anything — the mind has no shelf for it, and Chapter 8 is devoted to feeling just how big such numbers are. For now the point is simpler: you know exactly what it is, and you could recompute it.
Second question: all twelve words different, order mattering. Now the stages shrink: 2,048 options for the first word, 2,047 for the second, down to \(2{,}048 - 11 = 2{,}037\) for the twelfth. A falling product of twelve factors:
\[ 2{,}048 \times 2{,}047 \times \cdots \times 2{,}037 = 5{,}271{,}537{,}971{,}301{,}488{,}476{,}000{,}309{,}317{,}528{,}177{,}868{,}800. \]Place it next to the full count: forbidding repeats shrank the space by only about three percent. That makes sense — with only twelve draws from a list of 2,048, repeats were rare to begin with. Rules that forbid things barely move a count; the next rule moves one enormously.
Third question: all twelve words different, and order does not matter. Choosing 12 from 2,048:
\[ \binom{2{,}048}{12} = \frac{2{,}048!}{12! \; 2{,}036!} = 11{,}005{,}261{,}717{,}918{,}037{,}175{,}659{,}349{,}191{,}168. \]Still thirty-two digits — but the ordered count had forty. Dividing out the \(12!\) internal arrangements cost eight digits, a factor of \(12! = 479{,}001{,}600\). Order, it turns out, is worth a great deal.
Which of the three counts a thief must actually face — and what it would cost them to walk through it — is a question about attackers and money, not about counting. Chapter 11 answers it, using exactly these three numbers. And one warning belongs here, before anyone gets clever:
This chapter counts phrases; it says nothing about how to choose one. The one thing you must never do is invent the twelve words out of your own head — human-picked words are not the count you just computed, not anywhere close. Chapter 9 shows what happens, in the wild, to people who do.
Every count printed in this section appears in that four-line session. Run it; the card on the table becomes a number you own.
You now have the three tools. Choices multiply (Definition 1.1) — stages side by side, totals multiplied. A two-option stage doubles, and \(n\) of them give \(2^n\) (§1.3). Order mattering gives falling products and factorials (Definition 1.2); order not mattering divides the duplicates out and gives "\(n\) choose \(k\)" (Definition 1.3). And the card on the table is counted: \(2{,}048^{12}\), a falling product, and a choice — forty digits, forty digits, thirty-two.
Counting answers how many. It does not answer how likely — and "how likely" is the question the thief actually poses, because they will not try every phrase; they will try a few and hope. Turning counts into chances is Chapter 2's work, and it uses nothing you do not already have: every probability in this book is one counting answer divided by another.
Exercise 1.1 ★ Plates, by the principle. Compute the number of license plates with three letters followed by three digits, by hand or in Python. You should get exactly \(17{,}576{,}000\). Then: the state adds a fourth letter at the end. By what factor does the space grow? You should get exactly 26.
Exercise 1.2 ★ PIN arithmetic. How many more 6-digit PINs are there than 4-digit PINs — state it as a factor ("… times as many"). You should get exactly \(100\).
Exercise 1.3 ★★ Past a million. Using the doubling table in §1.3 — no calculator — find the smallest number of coin flips whose outcome-count exceeds one million. You should land on exactly \(20\) flips, at \(1{,}048{,}576\).
Exercise 1.4 ★★ A shelf and a loan. You have 5 paperbacks. (a) In how many orders can you shelve all five? (b) In how many ways can you choose 2 of them to lend a friend, if which-gets-shelved-first doesn't matter? You should get \(120\) and \(10\).
Exercise 1.5 ★★★ Twelve different words. Suppose the twelve words on the card must all be different, order still mattering. In Python, compute math.perm(2048, 12) and confirm it equals 5,271,537,971,301,488,476,000,309,317,528,177,868,800. Then divide it by 2048 ** 12 and confirm the ratio is about \(0.968\) — the repeat-free space is only about \(3\%\) smaller than the full one.
Exercise 1.6 ★★★ A friend says: "Choosing is just arranging with the duplicates divided out." Using the five-friends example of §1.5 — 20 ordered picks shrinking to 10 teams — explain precisely which duplicates the \(k!\) divides out, and why each unordered team is counted exactly \(k!\) times in the ordered count.
Sketches, not model answers — enough to check your reasoning against. The computational exercises embed their expected outputs in the exercise text.
Exercise 1.6. In the ordered count of \(5 \times 4 = 20\), a team is a sequence: Ann-then-Bo and Bo-then-Ann appear as two different entries. But a team has no sequence — those two entries are one team. How many entries does each team produce? As many as there are ways to arrange its own members, and \(k\) members arrange in \(k!\) ways; for \(k = 2\) that is \(2! = 2\) entries per team, so the 20 ordered picks contain each team twice and \(20 / 2 = 10\) is the true count. Nothing else is divided out — the \((n-k)!\) in the factorial form handles the unpicked friends, a separate matter: it is what converts "arrange all five" into "arrange just two" before the duplicate-division even begins.