Combinatorial proof

A combinatorial proof is a method of proving a statement, usually a combinatorics identity, by counting some carefully chosen object in different ways to obtain different expressions in the statement (see also double counting). Since those expressions count the same object, they must be equal to each other and thus the statement is established.

Related Topics:
Combinatorics - Identity - Double counting

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A statement is said to be proven combinatorially if a combinatorial argument, or counting argument, is used in the aforementioned fashion to justify the key steps of its proof.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

One simple example of a combinatorial proof is the following result on binomial coefficient C(n; k) (read n choose k):

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Proposition 1.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:C(n; k) = C(n; n − k).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Proof.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

We count the number of ways choosing k elements from an n-set.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

By definition, C(n; k) is the number of ways choosing k from n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

But each time we choose any k elements, we must also leave behind n − k elements, which is the same as choosing n − k elements (to leave behind).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

So this number must also equal C(n; n − k).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Box

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A slightly less trivial example is the following:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Proposition 2.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:C(n; k) = C(n − 1; k − 1) + C(n − 1; k) for all 1 ≤ k ≤ n − 1.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Proof.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

We count the number of ways choosing k elements from an n-set.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Again, by definition, C(n; k) is the number of ways choosing k from n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Since 1 ≤ k ≤ n − 1, we can pick a fixed element e from the n-set so that the remaining subset is not empty.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For each k-set, if e is chosen, there are C(n − 1; k − 1) ways to choose the remaining k − 1 elements among the remaining n − 1 choices; otherwise, there are C(n − 1; k) ways to choose the remaining k elements among the remaining n − 1 choices.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Thus, there are C(n − 1; k − 1) + C(n − 1; k) ways to choose k elements depending on whether e is included in each selection.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Box

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Problems that admit combinatorial proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a combinatorial proof can become very sophisticated. This technique is particularly useful in areas of discrete mathematics such as combinatorics, graph theory, and number theory.

Related Topics:
Discrete mathematics - Combinatorics - Graph theory - Number theory

~ ~ ~ ~ ~ ~ ~ ~ ~ ~