Double counting (proof technique)

In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set. In this technique, which van Lint & Wilson (2001) call “one of the most important tools in combinatorics,” one describes a finite set X from two perspectives leading to two distinct expressions for the size of the set. Since both expressions equal the size of the same set, they equal each other.

One example of the double counting method counts the number of ways in which a committee can be formed from n people, allowing any number of the people (even zero of them) to be part of the committee. That is, one counts the number of subsets that an n-element set may have. One method for forming a committee is to ask each person to choose whether or not to join it. Each person has two choices – yes or no – and these choices are independent of those of the other people. Therefore there are 2 × 2 × ... × 2 = 2ⁿ possibilities. Alternatively, one may observe that the size of the committee must be some number between 0 and n. For each possible size k, the number of ways in which a committee of k people can be formed from n people is the binomial coefficient

Therefore the total number of possible committees is the sum of binomial coefficients over k = 0, 1, 2, ... n. Equating the two expressions gives the identity

a special case of the binomial theorem. A similar double counting method can be used to prove the more general identity

(Garbano, Malerba & Lewinter 2003; Klavžar 2006).

Another theorem that is commonly proven with a double counting argument states that every undirected graph contains an even number of vertices of odd degree. That is, the number of vertices that have an odd number of incident edges must be even. In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands; for this reason, the result is known as the handshaking lemma.

...
Wikipedia