Double Counting
Count it twice, set the answers equal.
Choose a set, count it in two different ways, and equate. The identity that falls out is often one you could never have guessed directly. This is how most combinatorial identities are really proved.
The standard incarnation is counting incidences: sum the degrees of a graph's vertices and you get twice the number of edges. Counting pairs (person, handshake) gives the handshake lemma for free.
When a problem hands you a doubled quantity or an unexpected factor of two, double counting is usually lurking underneath.
Train it on Lemma
Double Counting unlocks at Level 4 of Lemma's eight-level ladder, with lessons that teach it and drills that make it stick. 125 lessons, 1206 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and every paid plan opens with 3 free days.
Find your levelMore techniques
- Constructive Counting & OvercountingBuild the object step by step, then divide by what you repeated.
- Modular ThinkingWhen the numbers are too big, shrink the universe.
- All 29 techniques →