Counting without listing

Combinatorics is the art of knowing how many things there are without producing them. Four rules do almost all of the work, and the fourth is the one people get wrong.

\binom{n}{k} \;=\; \frac{n!}{k!\,(n-k)!} \;=\; \binom{n-1}{k-1} + \binom{n-1}{k}

Every complexity analysis you have ever read rests on a counting argument, usually an unstated one. How many subsets, how many orderings, how many paths — the algorithm's cost is a count, and the analysis is the act of finding that count without enumerating the things being counted. This is the whole subject in one sentence, and everything that follows is technique.

The four rules#

Almost every elementary count is one of four moves, or a composition of them. They are worth stating precisely, because the errors people make are almost always a misapplication of the fourth.

SUM. If a thing is either an A or a B and never both, the count is |A| + |B|. The failure mode is forgetting the 'never both'.
PRODUCT. If a thing is an A followed independently by a B, the count is |A| × |B|. The failure mode is that the second choice depends on the first.
BIJECTION. If you can pair the things you want with things you can already count, the counts are equal. This is the most powerful of the four and the least used.
DIVISION. If your count sees every object exactly k times, divide by k. This is where the errors live.

The division rule is treacherous because it silently assumes the overcount is uniform — that every object is seen the same number of times. When it is not, the division is meaningless and the answer is confidently wrong. Necklaces are the standard counterexample: rotating a necklace of beads usually gives you a different arrangement, but a necklace of all one colour is fixed by every rotation, so it is overcounted once rather than n times.

Divide by the overcount only when the overcount is the same everywhere. It usually isn't, and that is where Burnside starts.

Bijections earn their keep#

The bijection rule deserves special attention because it converts hard counts into easy ones without any arithmetic at all. The classic: how many ways can you choose k items from n? Rather than reason about choices, pair each selection with a binary string of length n containing exactly k ones. Now the question is how many such strings there are, which is a question about arrangements, which you can already answer.

choose 3 from {a,b,c,d,e}          binary string of length 5
  {a, c, d}              <-->      1 0 1 1 0
  {b, d, e}              <-->      0 1 0 1 1
  {a, b, c}              <-->      1 1 1 0 0

The same object under two descriptions. Once the correspondence is exact in both directions, the counts are equal and you may work with whichever side is easier.

The discipline is to check both directions. A map that is onto but not one-to-one is an overcount, not a bijection, and it puts you back in rule four with all its hazards.

Why this generalises#

These four rules reappear, barely disguised, throughout the rest of this series. Inclusion-exclusion is the sum rule repaired for overlapping sets. Generating functions are the product rule made algebraic so that it composes. Graph colouring counts are bijections in disguise. Learn the four properly and the later material stops being a sequence of tricks.