How many eight-character passwords are there? How many addresses can a network have? At most how many attempts does it take to guess a PIN? These are counting questions, and almost all of them can be answered by combining a few elementary rules. Combinatorics sometimes looks like a collection of formulas to memorise; in fact every formula derives from these principles, and anyone who masters them can rebuild the formulas when needed.
The product rule
If a task consists of two stages, the first of which can be done in m ways and the second in n ways regardless of the choice made in the first, then the whole task can be done in m · n ways.
The rule extends to k stages: n₁ · n₂ · … · nₖ.
Examples:
- A 4-digit PIN: 10 · 10 · 10 · 10 = 10⁴ = 10,000 possibilities.
- An 8-character password drawn from 26 lower-case letters: 26⁸, about 2.09 · 10¹¹.
- A menu with 3 starters, 4 mains and 2 desserts: 3 · 4 · 2 = 24 different meals.
The product rule is the same one that gives the cardinality of a Cartesian product: |A × B| = |A| · |B|.
The sum rule
If an object can be chosen from a first group in m ways or from a second group in n ways, and the two groups are disjoint (no object belongs to both), then there are m + n choices in total.
Example: a password between 6 and 8 lower-case characters long. Passwords of different lengths are disjoint cases, so the total is 26⁶ + 26⁷ + 26⁸.
If the groups are not disjoint, the sum counts the shared elements twice; in that case you need the inclusion-exclusion principle.
Combining the two rules
Almost every real problem requires alternating sum and product. A reliable method:
- split the cases so that they are disjoint (sum rule);
- count each case as a sequence of independent choices (product rule).
Example: an identifier consists of 2 letters followed by 3 digits, or 3 letters followed by 2 digits (26-letter alphabet). First type: 26² · 10³ = 676,000. Second type: 26³ · 10² = 1,757,600. The two types are disjoint, because the position of the first digit differs. Total: 2,433,600.
The complement rule
It is often easier to count what you don't want and subtract it from the total.
Question: how many 8-character passwords, drawn from 26 lower-case letters and 10 digits, contain at least one digit?
Counting "at least one" directly is awkward: one digit, two digits, three… The complement is simple: passwords without digits number 26⁸. The total is 36⁸. So:
36⁸ − 26⁸ ≈ 2.82 · 10¹² − 2.09 · 10¹¹ ≈ 2.61 · 10¹²
Whenever "at least one" appears, the complement is the first thing to try.
The division rule
If a procedure counts every object exactly d times, the number of objects is the count divided by d.
Example: in how many ways can 5 people sit around a round table, if only relative positions matter? Arrangements in a row number 5 · 4 · 3 · 2 · 1 = 120. But each circular arrangement corresponds to 5 arrangements in a row, obtained by rotation. So there are 120 / 5 = 24 distinct ways.
The division rule, applied to permutations, is what produces binomial coefficients.
An application to security
Counting principles are the foundation for estimating the strength of a password or a key. The space of possibilities for a password of length L over an alphabet of N symbols is Nᴸ. It is often expressed in bits as L · log₂ N.
| Alphabet | N | bits per character |
|---|---|---|
| digits only | 10 | ≈ 3.32 |
| lower case | 26 | ≈ 4.70 |
| lower and upper case | 52 | ≈ 5.70 |
| letters and digits | 62 | ≈ 5.95 |
Two practical observations follow at once. First, length weighs more than the alphabet, because it sits in the exponent: adding two lower-case characters brings more bits than going from 26 to 62 symbols on an already long password. Second, these numbers only hold if each character is truly chosen at random. A password made up by a person, with a word and a number at the end, occupies a tiny part of the theoretical space. In my work, this distinction between theoretical and effective space is where I start every time I assess a password policy.
Counting also helps you read attempt limits. A 4-digit PIN that locks after 3 errors gives a guesser 3 chances in 10,000: it is the attempt limit, more than the length of the code, that really provides the protection.
In short
- Product rule: independent choices in sequence multiply.
- Sum rule: disjoint cases add.
- When "at least one" appears, count the complement and subtract.
- If every object is counted d times, divide by d.
- A password space is Nᴸ: length matters more than the alphabet, but only if the choice is random.
