A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Double counting counts the same set in two different ways to prove combinatorial identities. If two counting methods count the same objects, they must give the same result. This technique reveals hidden relationships between combinatorial quantities.
Identify a set to count, then describe two different counting methods for that set. Set the counts equal and simplify to derive an identity.
The double counting principle is one of the most elegant proof techniques in combinatorics. The core idea is simple: if you count the same finite set in two genuinely different ways, both counts must agree. From this obvious observation, remarkable identities fall out almost for free. The key skill is finding a set worth counting and then discovering two natural perspectives on it.
The handshake problem demonstrates the technique perfectly. Suppose a party has n people and everyone shakes hands with everyone else. How many handshakes occur? Count from the perspective of pairs of people: there are C(n,2) = n(n-1)/2 such pairs. Now count from the perspective of each person: each of the n people shakes hands with (n-1) others, giving n(n-1) total — but each handshake has been counted twice (once for each participant), so divide by 2. Both methods give n(n-1)/2. The identity is proved without algebra: it follows from counting the same handshakes two ways. In graph language, the sum of all vertex degrees equals twice the number of edges, because each edge contributes 1 to each of its two endpoints' degree counts.
A more powerful application proves combinatorial identities like the Vandermonde identity or the hockey stick identity for binomial coefficients. Consider counting the number of ways to choose a committee of k people from a group of n. That is C(n,k) by definition. Now imagine the group includes one special person, Alice. Either Alice is on the committee (choose the remaining k-1 from the other n-1 people) or she is not (choose all k from the other n-1). This gives C(n-1,k-1) + C(n-1,k) = C(n,k) — Pascal's identity, proved by double counting a single set from two perspectives.
The connection to your prerequisite counting principles is direct: you already know how to count using multiplication, addition, and combinations. Double counting adds a proof technique on top — instead of computing a quantity, you argue that two formulas must be equal because they describe the same quantity. This is the gateway to the bijection principle: if you can biject two sets, they have the same size. Double counting is a special case where the "bijection" is implicit in the two counting arguments. Mastering this technique trains you to see counting problems as having structure worth exploiting, not just formulas to apply.