Double counting

Summary

Double counting is a proof technique in combinatorics. To prove that two expressions are equal, one shows that both count the elements of the same finite set. Each expression comes from a different way to count that set.

A common form uses a relation $R \subseteq A \times B$ between finite sets $A$ and $B$. For $a \in A$, let $d(a)$ be the number of $b \in B$ with $(a, b) \in R$. For $b \in B$, let $e(b)$ be the number of $a \in A$ with $(a, b) \in R$. Then both sums count the pairs in $R$, so $$\sum_{a \in A} d(a) = |R| = \sum_{b \in B} e(b).$$