Double Counting

Count one set two ways and equate the totals.

The idea

Double counting proves an identity or a bound by counting one finite set in two different ways. The two counts must agree, because they measure the same set, and the equation between them is the result.

The usual setup counts a set of pairs. To relate two kinds of object, form the set of pairs that match one object of each kind. Count the pairs by grouping on the first coordinate, count them again by grouping on the second, and equate the totals. The resulting equation relates the two kinds of object, which neither grouping shows on its own.

Reach for double counting when a problem asks you to prove that two counts are equal, or to bound one count by another, and direct enumeration is out of reach. Finding the right set to count twice usually settles such a question in a line.

Ways to work on it

• Walkthrough. Count (vertex, edge) pairs two ways to prove the handshake lemma.
• Practice. Find a hidden total by counting membership pairs two ways.
• Hardest. Derive an algebraic identity by double counting.

Not sure where to start? Take the ten-question placement test.