Combinatorial Proof - The Benefit of A Combinatorial Proof

The Benefit of A Combinatorial Proof

Stanley (1997) gives an example of a combinatorial enumeration problem (counting the number of sequences of k subsets S₁, S₂, ... S_k, that can be formed from a set of n items such that the subsets have an empty common intersection) with two different proofs for its solution. The first proof, which is not combinatorial, uses mathematical induction and generating functions to find that the number of sequences of this type is (2k −1)n. The second proof is based on the observation that there are 2k −1 proper subsets of the set {1, 2, ..., k}, and (2k −1)n functions from the set {1, 2, ..., n} to the family of proper subsets of {1, 2, ..., k}. The sequences to be counted can be placed in one-to-one correspondence with these functions, where the function formed from a given sequence of subsets maps each element i to the set {j | i ∈ S_j}.

Stanley writes, “Not only is the above combinatorial proof much shorter than our previous proof, but also it makes the reason for the simple answer completely transparent. It is often the case, as occurred here, that the first proof to come to mind turns out to be laborious and inelegant, but that the final answer suggests a simple combinatorial proof.” Due both to their frequent greater elegance than non-combinatorial proofs and the greater insight they provide into the structures they describe, Stanley formulates a general principle that combinatorial proofs are to be preferred over other proofs, and lists as exercises many problems of finding combinatorial proofs for mathematical facts known to be true through other means.