Double Counting is the habit of counting the same set of incidences in two ways to prove identities or bounds. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
$$\sum_{v} \deg(v) = 2\,|E| \quad (\text{count edge-endpoints two ways})$$
Count the same collection of things in two different ways; since both counts equal the same total, they equal each other.
Why It Works
1
Choose a set of 'incidences' (object–object pairs) and count its size in two ways.
2
Because both expressions count one and the same set, they must be equal — this equation is the payoff.
3
Example incidences: edge-endpoints in a graph. Counting per vertex gives $\sum_v \deg(v)$; counting per edge gives $2$ endpoints each, so $2|E|$.
4
Setting the two counts equal yields the Handshake Lemma $\sum_v \deg(v) = 2|E|$, and the same trick proves many binomial identities.
Worked Examples
Example 1
At a party with $6$ people, everyone shakes hands with everyone else once. How many handshakes occur?
1
Count from each person's side: each of $6$ people shakes $5$ hands, giving $6 \cdot 5 = 30$ endpoints.
2
But each handshake has $2$ endpoints and so was counted twice in that total.
3
Divide by $2$: the number of handshakes is $\dfrac{30}{2} = 15$.
4
Check: this is $\binom{6}{2} = 15$, the number of unordered pairs.
Answer:
$15$
Warm-up
Prove the identity $1 + 2 + 3 + \cdots + n = \binom{n+1}{2}$ by counting something two ways.
1
Count the number of ways to choose $2$ distinct elements from $\{1, 2, \ldots, n+1\}$; this is $\binom{n+1}{2}$ by definition.
2
Now count the same pairs by their larger element. If the larger element is $k+1$ (for $k = 1, \ldots, n$), the smaller can be any of $\{1, \ldots, k\}$: that is $k$ choices.
3
Summing over the possible larger elements gives $1 + 2 + \cdots + n$ pairs.
4
Both expressions count the same set of pairs, so $1 + 2 + \cdots + n = \binom{n+1}{2}$.
A committee has $10$ members; each member belongs to exactly $3$ of the committee's subcommittees, and each subcommittee has exactly $5$ members. How many subcommittees are there?
1
Count the (member, subcommittee) incidence pairs — i.e. memberships — two ways.
2
From the members' side: each of $10$ members has $3$ memberships, giving $10 \cdot 3 = 30$ incidences.
3
From the subcommittees' side: each of $s$ subcommittees has $5$ members, giving $5s$ incidences.
4
Equate: $5s = 30$, so $s = 6$.
Answer:
$6$
Olympiad / Challenge
Prove the identity $\sum_{k=0}^{n} k\binom{n}{k} = n\,2^{n-1}$ by double counting.
1
Count pairs $(\text{committee}, \text{leader})$ where a committee is any subset of $n$ people and the leader is a chosen member of that committee.
2
First way: pick a committee of size $k$ in $\binom{n}{k}$ ways, then choose its leader among the $k$ members; summing over all sizes gives $\sum_{k=0}^{n} k\binom{n}{k}$.
3
Second way: pick the leader first ($n$ choices), then freely include or exclude each of the remaining $n-1$ people, giving $n \cdot 2^{n-1}$.
4
Both count the same (committee, leader) pairs, so $\sum_{k=0}^{n} k\binom{n}{k} = n\,2^{n-1}$.
Answer:
$\sum_{k=0}^{n} k\binom{n}{k} = n\,2^{n-1}$.
Going Deeper
The general move is to count a set of 'incidences' (object pairs, flags, or tuples) by summing over one type of object, then over the other; the two sums are equal because they count one set. This is the standard proof technique for binomial identities (Vandermonde, the committee-leader identity, hockey stick) and for combinatorial design constraints.
It is everywhere in graph theory (the handshake lemma $\sum \deg(v) = 2|E|$), in counting incidences between points and lines, and in 'each X belongs to exactly $r$ Y's' problems where you solve for an unknown count. The signature is two different but provably-equal expressions for the same total.
Pitfall: you must count the SAME set both ways — define the incidence set explicitly and confirm each side enumerates exactly it. The classic error is an asymmetry (e.g. counting ordered pairs one way and unordered the other), which introduces a stray factor of $2$ and breaks the identity. State precisely what a single counted object is before writing either sum.
Spot the Signal
Look for problems where the key step is counting the same set of incidences in two ways to prove identities or bounds.
You can describe the hard part as counting the same set of incidences in two ways to prove identities or bounds, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the counting object that calls for double counting, then rewrite the givens around it.
Name the relation that makes Double Counting legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Double Counting just because the surface looks familiar; verify the required condition first.
Applying Double Counting because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let double counting reveal the counting structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is counting the same set of incidences in two ways to prove identities or bounds.