Combinatorial Proof

In mathematics, the term combinatorial proof is often used to mean either of two types of proof of an identity in enumerative combinatorics that either states that two sets of combinatorial configurations, depending on one or more parameters, have the same number of elements (for all values of the parameters), or gives a formula for the number of one such set of configurations in terms of the parameters:

• A bijective proof, which exhibits a bijection, i.e. a one-to-one correspondence, between the two sets, or (in the case of a formula) between the given set and a set obviously counted by the formula.

• A proof by double counting. Some combinatorial set S, often different from the ones in question, is counted in two different ways, and from the equality of the numbers so found the desired identity is deduced. The two ways of counting S must each be by establishing a bijection of S with a set obviously counted by the number found.

The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics. However, as Glass (2003) writes in his review of Benjamin & Quinn (2003) (a book about combinatorial proofs), these two simple techniques are enough to prove many of the important theorems in combinatorics and number theory.