How a double counting proof is actually built

A finished double counting proof reads like a card trick. Someone announces that they are going to count the pairs (person, handshake), counts them twice, and an identity nobody could have guessed drops out of the equals sign. It is the most quietly impressive move in olympiad combinatorics, and the one students copy worst, because the write-up hides the only decision that mattered.

So here it is explained forwards. Every double counting proof fits the same three-line skeleton, and all the examples below are that skeleton with different furniture.

The skeleton

1. Name a finite set $S$, and say exactly what one of its elements is.
2. Count $|S|$ one way.
3. Count $|S|$ a second way, and equate.

Steps 2 and 3 are bookkeeping. Step 1 is the proof. If you have ever read one of these identities and had no idea where to begin, you were stuck on step 1 without knowing it, because step 1 is the step a write-up prints as though it were obvious.

The example that teaches the shape

The handshake lemma: in any finite gathering, evenly many people have shaken hands an odd number of times.

Let $S$ be the set of pairs (person, a handshake they took part in). Counting by person, each person contributes as many pairs as they have handshakes, so $|S| = \sum_v \deg(v)$. Counting by handshake, each handshake has exactly two ends and so contributes exactly two pairs, giving $|S| = 2|E|$. The degree sum is therefore even, and a sum of integers is even only when evenly many of them are odd.

Notice what $S$ was: a set of pairs, one component from each of the two kinds of object the problem talks about. That is not a coincidence, and it is the most useful sentence on this page.

Step 1 in practice: you are hunting for incidences

Nearly every double count runs over pairs $(X, Y)$ where $Y$ is somehow inside or attached to $X$. Vertex and edge at it. Committee and member of it. Subset and element of it. Point and line through it. Student and club they joined. Once you have that set:

• counting $X$ first, then its $Y$s, gives one expression;
• counting $Y$ first, then the $X$s it sits in, gives the other;
• and the identity is nothing more than the statement that two orderings of one list have the same length.

So when a problem hands you two kinds of object with any notion of one belonging to the other, you already have a candidate for $S$. Try it before you try anything clever.

The one you would never reach by algebra

Count committees of size $k$ drawn from $n$ people, each committee with a designated chair.

Committee first: choose the $k$ members in $\binom{n}{k}$ ways, then pick the chair from among them in $k$ ways. Chair first: choose the chair in $n$ ways, then fill the remaining $k-1$ seats from the other $n-1$ people in $\binom{n-1}{k-1}$ ways. One set, two counts, so

$$k\binom{n}{k} = n\binom{n-1}{k-1}.$$

You can also get there by expanding factorials, and you will learn nothing doing it. The double count tells you why the identity holds, which is the thing a marker is actually reading for.

The two default second counts

When the objects are subsets, two moves cover most of what you will meet.

Count by size. Every subset of an $n$-element set is counted once by deciding each element in or out, which gives $2^n$, and once by sorting the subsets into piles according to how large they are, which gives $\sum_k \binom{n}{k}$. That is the whole proof, and it never mentions the binomial theorem.

Split on one distinguished element. Pascal's identity falls out the moment you ask whether a $k$-subset of $\{1, \dots, n\}$ contains the element $n$. The ones that do are a $(k-1)$-subset of everything else; the ones that do not are a $k$-subset of everything else. Counting the pile whole and counting it in two parts must agree, so $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

Double counting is not bijection, and the confusion costs time

Both moves end with two counts being equal, so they get muddled. They are not the same thing.

• Double counting: one set, counted two ways. Both sides of your equation are $|S|$.
• Bijection: two sets, matched element against element. What you produce is a map, and you owe a proof that it is reversible.

Showing that a set has as many even-sized subsets as odd-sized ones is a bijection problem, not a double counting one. Toggle whether the element $1$ is in or out: the map changes the size by one, so it sends even to odd and odd to even, and doing it twice returns you to where you started. There is no single set here to count twice. There are two families to pair off. Reaching for a double count on that costs a quarter of an hour and produces nothing.

The rough test: if what you want is an equation with a product or a sum on each side, double count. If what you want is "these two families are the same size", build the map.

Where they go wrong

Three failure modes, roughly in the order they bite.

1. The two counts are counting different sets. This is the classic near-miss, and the usual cause is ordering: you counted arrangements one way and unordered selections the other. It is the same disease as an uncorrected overcount, and constructive counting is where you learn to see the stray factor.
2. The count is not exact. "About $n$ of them" is not a count. If you cannot say precisely how many, the equals sign is a lie and the proof is worth nothing.
3. The set is never named. Write-ups that open with "consider the sum of the degrees" are hard to read and, under a rubric, drop the setup mark even when every number after it is right.

One more, done properly, in a single line: the number of two-edge paths in a graph is $\sum_v \binom{\deg v}{2}$, because every such path has exactly one middle vertex, and choosing that vertex and then two of its neighbours builds each path exactly once. Set named, counted, done.

What to practise

Do not solve identities. Take five of them and, for each, write three lines only: what $S$ is, the count one way, the count the other. You will get through five in the time one full write-up takes, and step 1 is the only part you are actually short of.

Lemma teaches this as a named technique rather than as a trick you happen to meet twice. The double counting page has the statement, the incidence pattern and where it sits in the ladder. The problem archive carries the counting problems above in full, with difficulty and expected time on each. And the daily problem posts a new one every morning in three tiers, no account needed, which is a cheap way to keep the habit warm between sessions.