Jul 31

Ways - Combinatorial proof

By admin
Add comments
Uncategorized

The term combinatorial proof is often used in either of two senses:

  • A proof by double counting. A combinatorial identity is proven by counting some carefully chosen object in two different ways to obtain different expressions in the statement. Since those expressions count the same object, they must be equal to each other and thus the statement is established. Finding such a proof generally requires seeing the two expressions as answers and seeking a corresponding question. For this reason, this technique has been colloquially described as Jeopardy! proof, after the TV game show with the gimmick of providing answers and requiring questions.
  • A bijective proof. Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them.


Examples


Double counting

A subcommittee of k members is chosen from a committee of n members, and then one of the k members of the subcommittee is chosen to be the chair. The number of ways to do this is

<math>{n \choose k} k.</math>

Alternatively, we first choose the chair from among all n members of the original committee and then choose the k − 1 other subcommittee members from among the n − 1 other members of the original committee. The number of ways to do this is

<math>n{n - 1 \choose k - 1}.</math>

Therefore, we conclude that

<math>{n \choose k}k = n{n - 1 \choose k - 1}.</math>

A similar technique proves Vandermonde’s identity.


Bijective proof

Suppose we wish to show that the number of size-k subsets of a size-n set is the same as the number of size-(n − k) subsets of a size-n set, i.e., that

<math>{n \choose k} = {n \choose n - k}.</math>

This can be accomplished by exhibiting a bijection between the set of all size-k subsets and the set of all size-(n − k) subsets. One such bijection—probably the simplest—is the correspondence between each size-k subset and its complement relative to the larger size-n set.


Benefit of the approach

Any correct mathematical proof of a result is completely sufficient to establish the truth of that result, so in that sense multiple proofs of a single result are interchangeable. But a proof is often valued not only for demonstrating that a result holds, but also for illustrating why it holds. From this perspective, combinatorial proofs are often highly sought after.

As an example, consider again the binomial coefficient, the number of k-element subsets that can be formed from an n-element set. The well-known formula for this is

<math> {n \choose k} = \frac{n!}{k! (n-k)!}, </math>

and it can be proven by mathematical induction. But writing—or reading—such a proof of this formula is a dry exercise in using a few definitions and performing some routine arithmetic and algebra. Now consider this combinatorial proof that uses double counting…

Question: In how many ways can you select k children for special honors from a class of size n?
Answer 1: This amounts to selecting a k-subset, which can be done in <math>n \choose k</math> ways.
Answer 2: Line the children against the wall and merely take the first <math>k</math> of them, which can be done in <math>n!</math> ways. But <math>n!</math> is an overestimate of our answer because we do not care how the honorees, the first <math>k</math> children, arrange themselves in line, so we must divide by <math>k!</math>. And this is still an overestimate, because we also don’t care how the remaining <math>n - k</math> children are arranged, so we must divide by a further <math>(n - k)!</math>.
Conclusion: Since they are answers to the same question, answers 1 and 2 must be equal.

Resources

This entry was posted on Tuesday, July 31st, 2007 at 2:16 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. Responses are currently closed, but you can trackback from your own site.

Comments are closed.