Counting Principles

Combinatorics is the art of counting without listing. Ask "how many PINs are there?" and nobody sane writes them all out — ten thousand of them — and ticks them off. Instead we count the structure of the choices: four slots, ten digits each. The whole subject grows from two almost embarrassingly simple rules for combining choices, and the discipline of deciding, for a given problem, which rule applies. Get those two reflexes right and you can count things that could never be listed in the lifetime of the universe.

The two rules answer two different questions. The sum rule handles "this OR that" — a choice between alternatives. The product rule handles "this AND then that" — a sequence of choices made together. Almost every counting error a beginner makes is really the error of reaching for the wrong one of these two.

Let a task be built from choices among finite sets. Then:

Sum rule. If a thing can be done in one of two mutually exclusive ways — a ways of the first kind, b of the second, with no overlap — the number of ways to do it is a + b. In set terms, for disjoint A, B: |A \cup B| = |A| + |B|.
Product rule. If a task is a sequence of independent stages — the first done in a ways, the second (for each first outcome) in b ways — the whole task is done in a \times b ways. In set terms: |A \times B| = |A| \cdot |B|.

The product rule, made of dots

Why does "AND" multiply? Lay the outcomes out as a grid. If a breakfast is a m-way choice of drink and then a n-way choice of pastry, every complete breakfast is a pair — a cell in an m \times n lattice. Counting the cells is exactly multiplying the sides. Drag the sliders: the readout is not a formula you memorise, it is the number of dots you can see.

This is why the product rule chains: three stages of sizes a, b, c give a \cdot b \cdot c — the grid just gains a dimension. A four-digit PIN is four stages of size ten, so 10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10{,}000. A licence plate of three letters then three digits is 26^3 \cdot 10^3 = 17{,}576{,}000. The exponential explosion of combinatorics is the product rule, applied over and over.

Worked examples: which rule, and why

1 — A menu (product, then sum)

A café offers a set lunch: one of 4 starters and one of 5 mains, for 4 \cdot 5 = 20 lunches. Separately it offers a soup-only option: one of 3 soups. A "meal" is a set lunch or a soup — mutually exclusive — so the sum rule joins the two counts: 20 + 3 = 23 meals. Notice the phrasing does the work: the "and" inside the set lunch multiplied; the "or" between the two menus added.

2 — Passwords with a constraint (subtract the bad)

How many 3-letter strings use at least one vowel (from the 26-letter alphabet, 5 vowels)? Counting these directly is fiddly. Count the complement instead: all strings minus the vowel-free ones. Total strings 26^3 = 17{,}576; consonant-only strings 21^3 = 9{,}261; so the answer is 17{,}576 - 9{,}261 = 8{,}315. "Total minus bad" is the sum rule in disguise (the good and bad are disjoint and exhaust everything) and it is one of the most useful moves in the whole subject.

3 — Counting by a bijection

How many subsets does a set of n elements have? Line the elements up and walk down them making one yes/no choice per element — "in the subset?" — a sequence of n two-way choices, so 2^n by the product rule. The deep move here is that we did not count subsets at all: we found a bijection between subsets and length-n binary strings, then counted the strings. Whenever two collections are in exact one-to-one correspondence they have the same size — so a hard count becomes an easy one you already know.

Bijective counting: the master principle

A bijection — a function that is one-to-one and onto — is the counter's most powerful tool, because it turns counting into re-describing. If you can match the things you want to count, exactly and without repeats, against things you can count, you are done.

If there is a bijection f : A \to B between finite sets, then |A| = |B|.
So to count A, it suffices to build a bijection from A to any set B whose size you already know.

Example: the number of ways to walk from corner (0,0) to (m,n) on a grid using only unit steps right (R) and up (U) is the number of strings with m R's and n U's — a bijection between paths and words. Counting the words is a permutations question you will meet on the next page. The lesson: the sum rule, the product rule, complementary counting, and bijections are the entire toolkit — everything later is these four, wielded cleverly.

Drop the "mutually exclusive" and the sum rule lies. Suppose a class has 18 students who play football and 12 who play chess. How many play football or chess? Not 30 — unless nobody does both. Anyone who plays both got counted twice, once in each group. If 5 play both, the honest count is 18 + 12 - 5 = 25. That correction — subtract the overlap — is the seed of the inclusion–exclusion principle, which generalises it to any number of overlapping sets. The bare sum rule is just its special case where every overlap is empty.

Three classic slips, all about choosing the wrong principle:

"AND" does not always multiply blindly. The product rule needs each later stage to have the same number of options regardless of earlier choices. Choosing a president and then a vice-president from 10 people is 10 \cdot 9 (not 10 \cdot 10) — once someone is president, only 9 remain. The count per stage may change even though it stays the same size at each step; that is exactly the permutation idea.
"OR" only adds when the cases can't overlap. If they can, adding double-counts — reach for inclusion–exclusion, or make the cases disjoint by construction.
Don't count the same outcome under two different stories. Overcounting is the beginner's disease. The cure is a bijection: pin down exactly what one "outcome" is, and check your counting matches each outcome once and only once.