Double counting (proof technique)

Double counting, also known as counting in two ways, is a combinatorial proof technique that involves counting the size of a set in two distinct ways. By establishing two different expressions for the same quantity, we can then equate these expressions to derive a combinatorial identity or prove a relationship between different parameters.

The basic principle behind double counting relies on the fundamental fact that if a set S has a finite number of elements, denoted by |S|, then the number of elements in S is independent of the method used to count them. Therefore, if we can find two different valid methods of counting the elements of S, resulting in expressions A and B, we can conclude that A = B.

The success of this technique depends on choosing a set S that can be easily and naturally counted in two different ways, often by considering different perspectives or decompositions of the set. The two counting methods should preferably lead to expressions that are relatively simple and allow for a meaningful comparison or simplification once they are equated.

Applications of double counting are widespread in combinatorics, including proofs related to graph theory, set theory, and number theory. The technique is valued for its elegance and ability to provide insightful proofs without relying on complex algebraic manipulations.