Mathematics.

proof techniques

Combinatorial Proofs

Combinatorics35 minDifficulty4 out of 10

You should know: combinations

Overview

A combinatorial proof establishes an identity by showing that both sides count the same collection of objects, rather than by algebraic manipulation. Two main styles exist: a double-counting proof shows a single set counted in two different ways gives both sides of the equation, while a bijective proof exhibits a one-to-one correspondence between two differently-described sets. Combinatorial proofs are prized for being often shorter and more illuminating than algebraic proofs, directly revealing why an identity is true.

Intuition

To prove ∑ₖC(n,k) = 2ⁿ combinatorially, count the subsets of an n-element set S in two ways. On one hand, every subset is determined by making an independent in/out choice for each of the n elements, giving 2ⁿ total subsets. On the other hand, you can group subsets by their size k and count C(n,k) subsets of each size, summing over all k from 0 to n. Since both computations count exactly the same set of objects (all subsets of S), the two expressions must be equal — no algebra required. This is the essence of combinatorial proof: find a set of objects, count it two different ways, and the identity falls out.

Formal Definition

Definition

The two standard combinatorial proof techniques can be stated schematically:

∣S∣=A=B  ⟹  A=B(double counting: count set S two ways)|S| = A = B \implies A = B \quad \text{(double counting: count set } S \text{ two ways)}
Double counting
if f:X→Y is a bijection, then ∣X∣=∣Y∣(bijective proof)\text{if } f: X \to Y \text{ is a bijection, then } |X| = |Y| \quad \text{(bijective proof)}
Bijective proof
∑k=0n(nk)=2n\sum_{k=0}^{n} \binom{n}{k} = 2^n
Classic double-counting example: subsets of an n-set

Worked Examples

  1. Count subsets of {a,b,c} directly: each element is either in or out, giving 2^3 = 8 total subsets.

    23=82^3 = 8

  2. Count the same subsets grouped by size: sizes 0,1,2,3 give C(3,0)=1, C(3,1)=3, C(3,2)=3, C(3,3)=1.

    1+3+3+1=81+3+3+1 = 8

Answer: Both counts equal 8, proving the identity for n=3 (and the same argument works for any n).

Practice Problems

Difficulty 5/10

Give a combinatorial (double-counting) proof of Pascal's rule C(n,k) = C(n-1,k-1) + C(n-1,k), and verify it numerically for n=5, k=2.

Difficulty 6/10

Verify Vandermonde's identity C(5,2) = sum_i C(2,i)C(3,2-i) numerically as a check on the combinatorial proof (splitting a group of 2 men and 3 women).

Difficulty 4/10

Verify C(n,k)=C(n,n-k) numerically for n=6, k=2.

Quiz

A combinatorial proof of an identity A = B typically works by:
The bijection used to prove C(n,k) = C(n,n-k) is:
The identity ∑ₖC(n,k)=2ⁿ is proved combinatorially by counting:

Summary

  • Combinatorial proofs establish identities by counting the same collection of objects in two ways (double counting) or by finding a bijection.
  • They tend to be shorter and more insightful than algebraic proofs, revealing the 'why' behind an identity.
  • Classic examples include Pascal's rule, the symmetry identity C(n,k)=C(n,n-k), and Vandermonde's identity.

References

  1. WebsiteWikipedia — Combinatorial proof