Counting Without Listing

How strong is an 8-character password? How many items before a hash function collides? How many test cases does exhaustive coverage need? How many ways can a scheduler order these jobs?

All four are the same question: how many things are in a set that is far too large to write down. Combinatorics answers it by counting structure rather than objects, which is why it produces an exact number for a set with more members than there are atoms nearby.

Key idea: Counting is not arithmetic on a list. It is decomposing a choice into independent stages, working out how many options each stage has, and combining those numbers with two rules. Almost everything else in this lesson is a special case of doing that carefully.

The product rule. If a task is a sequence of independent stages with $n_1, n_2, \dots, n_k$ options each, the number of outcomes is the product $n_1 \times n_2 \times \cdots \times n_k$. Stages that happen together multiply.

The sum rule. If a task is one of several mutually exclusive alternatives, the counts add. Choices that are alternatives to each other add.

An 8-character password over the 95 printable ASCII characters is eight independent stages of 95 options:

$95^8 = 6{,}634{,}204{,}312{,}890{,}625 \approx 6.6 \times 10^{15}$

That number sounds enormous and is not. At $10^{12}$ guesses per second, a rate modern hardware reaches against a weak hash, the entire space falls in under two hours. Counting is what turns a vague feeling about security into a decision.

Almost every counting mistake is choosing the wrong one of these two.

$P(n, k) = \frac{n!}{(n-k)!} \qquad\qquad C(n, k) = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}$

Permutations $P(n,k)$ count ordered selections: which three finish first, second and third. Combinations $C(n,k)$ count unordered ones: which three made the team. The only difference is the $k!$ in the denominator, dividing out the orderings of each chosen set, since order no longer distinguishes them.

Try it: A lottery draws 6 numbers from 49 and order is irrelevant. $C(49,6) = 13{,}983{,}816$, so a single ticket wins about once in fourteen million. If order mattered it would be $P(49,6)$, which is 720 times larger, because $6! = 720$ orderings collapse into each unordered draw.

The sum rule requires alternatives to be mutually exclusive. When they overlap, adding double-counts the overlap, and inclusion-exclusion is the correction:

$|A \cup B| = |A| + |B| - |A \cap B|$

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

The alternating signs continue for more sets, adding odd-sized intersections and subtracting even-sized ones.

In practice: This is the same correction a query planner applies when estimating how many rows match several predicates, and the same one you need when reporting "users who did A or B" from two overlapping cohorts. Adding the two cohort sizes is the single most common reporting error in analytics, and it always overstates.

If you put $n+1$ items into $n$ boxes, some box holds at least two. Nobody disputes it, and it proves things that look much harder.

• Lossless compression cannot shrink every input. There are fewer short strings than long ones, so no injective map from all $n$-bit inputs into shorter outputs exists. Any compressor that shrinks some inputs must expand others.
• Hash collisions are guaranteed, not merely likely. A hash maps an unbounded input space into a fixed number of outputs, so collisions exist by counting. Cryptographic strength is about being unable to find them, never about their absence.
• Two people in London have the same number of hairs. A head holds fewer than a million hairs and the city holds millions of people.

Key idea: The pigeonhole principle proves existence without construction. It tells you a collision is there and offers no help at all in locating it, which is exactly the gap cryptography lives in.

The calculation is easier backwards. Compute the probability that everyone differs, which is a clean product, then subtract from 1:

$P(\text{shared}) = 1 - \frac{365}{365} \cdot \frac{364}{365} \cdots \frac{365 - n + 1}{365}$

Counting the complement instead of the event is one of the most reliable moves in combinatorics, and it works here because "all distinct" is a product of independent-looking choices while "at least one match" is not.

The shape is the point. It climbs slowly, then steeply through the middle, then flattens against 100 percent. By 50 people it is 97 percent and by 70 it is a near certainty, in a room holding a fifth of the number of days in a year.

The reason is that pairs, not people, are what collide, and $n$ people make $\binom{n}{2}$ pairs, which grows quadratically. Doubling the room roughly quadruples the opportunities for a match.

Replace 365 with the size of a hash output space and the birthday calculation becomes a security parameter. A collision becomes likely after roughly $\sqrt{N}$ items, not $N$, so an $n$-bit hash gives you about $n/2$ bits of collision resistance.

Gotcha: A 32-bit hash sounds like four billion possibilities and collides after about seventy-seven thousand entries. That is a medium-sized table, not an astronomical one, and it is why 32-bit checksums are fine for detecting accidental corruption and useless as identifiers.

Python's standard library has the exact functions, and using them beats hand-rolled factorials that overflow or lose precision.

import math
from itertools import combinations, permutations

math.comb(49, 6)          # 13983816   unordered
math.perm(49, 6)          # 10068347520 ordered
math.factorial(20)        # exact, arbitrary precision

# enumerate only when the count is small enough to justify it
len(list(combinations(range(49), 6)))   # same 13983816, minutes and gigabytes

Gotcha: The habit of checking a count by enumerating stops working almost immediately. combinations over 49 items taken 6 at a time is already fourteen million tuples. Verify small cases by enumeration, then trust the formula: that pattern, small case by brute force and general case by argument, is what the next lesson formalises as proof by induction.

Most counting errors are not arithmetic. They are misreading the structure of the choice, and a fixed procedure catches nearly all of them.

1. Describe one outcome precisely. If you cannot say exactly what a single element of the set looks like, you are not ready to count them.
2. Ask whether order distinguishes outcomes. Permutation if yes, combination if no. Ask it explicitly rather than assuming.
3. Ask whether repetition is allowed. Passwords repeat characters; lottery draws do not, and the formulas differ.
4. Decompose into stages, and check independence. The product rule needs each stage's option count to be the same whatever the earlier stages chose.
5. Check for overlap and for double counting. If two different stage sequences produce the same outcome, divide; if alternatives overlap, use inclusion-exclusion.
6. Sanity-check on a tiny case. Set $n = 3$ and count by hand. A formula that fails at 3 fails everywhere.