Combinatorial Proofs

Combinatorial proof is a perfect way of establishing certain algebraic identities without resorting to any kind of algebra. For example, let's consider the simplest property of the binomial coefficients:

To prove this identity we do not need the actual algebraic formula that involves factorials, although this, too, would be simple enough. All that is needed to prove (1) is the knowledge of the definition: C(n, k) denotes the number of ways to select k out n objects without regard for the order in which they are selected. To prove (1) one needs to observe that whenever k items are selected, n-k items are left over, (un)selected of sorts. So that proving (1) becomes a word usage matter. (In this example, another simple proof is by introducing m = n - k, from which k = n - m so that (1) translates into an equivalent form C(n, n - m) = C(n, m).)

As another example, the identity

which is a consequence of the binomial theorem

admits a combinatorial interpretation. The left hand side in (2) represents the number of ways to select a group -- empty or not -- of items out of a set of n distinct elements. The first term gives the number of ways not to make any selection, which is 1. The second term gives the number of ways to select one item (which is n), etc. What does the right hand side represent? Exactly same thing. Indeed, with every selection of items from a given set we can associate a function that takes values 0 or 1. A selected element is assigned value 1, while an unselected element is assigned value 0. If for the sake of counting convenience, the elements of the set are ordered with indices 1, ..., n, then every selection from the set is represented by a string of 0's and 1's; the total number of such strings is clearly the right hand side in (2): 2ⁿ.

Thus a combinatorial proof consists in providing two answers to the same question. But not to forget, finding the question to be answered in two ways is conceivably the most important part of the proof. As a matter of convention, it is often convenient to think of sets and their elements as groups of students and of selections of elements as endowing them with a membership on a committee.

For a third example, consider the popular identity underlying the Pascal triangle:

I'll provide more examples plucked mostly from an outstanding and easily available book by A. T. Benjamin and J. J. Quinn.

Combinatorial Proofs

1. k·C(n, k) = n·C(n - 1, k - 1), see Lucas' Theorem.
2. C(n, 1) + 2·C(n, 2) + 3·C(n, 3) + ... + n·C(n, n) = n2^n-1, see Ways To Count.

References

1. V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995
2. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
3. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

Copyright © 1996-2008 Alexander Bogomolny