Editing Combinatorial proof (section)

== The benefit of a combinatorial proof ==  <!-- Binomial coefficient links here -->

{{harvtxt|Stanley|1997}} gives an example of a [[combinatorial enumeration]] problem (counting the number of sequences of ''k'' subsets ''S''<sub>1</sub>, ''S''<sub>2</sub>, ... ''S''<sub>''k''</sub>, that can be formed from a set of ''n'' items such that the intersection of all the subsets is empty) with two different proofs for its solution. The first proof, which is not combinatorial, uses [[mathematical induction]] and [[generating function]]s to find that the number of sequences of this type is (2<sup>''k''</sup>&nbsp;&minus;1)<sup>''n''</sup>. The second proof is based on the observation that there are 2<sup>''k''</sup>&nbsp;&minus;1 [[proper subset]]s of the set {1, 2, ..., ''k''}, and (2<sup>''k''</sup>&nbsp;&minus;1)<sup>''n''</sup> 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''&nbsp;|&nbsp;''i''&nbsp;&isin;&nbsp;''S''<sub>''j''</sub>}.

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.