Mathwords logoMathwords

Combinatorial Proof — Definition & Example

A combinatorial proof is a way to prove that two expressions are equal by showing that both count the same collection of objects. The equality comes from a counting argument instead of algebra.

A combinatorial proof of an identity A=BA = B (with A,BA, B nonnegative integers depending on parameters such as nn and kk) uses one of two methods. In a double-counting proof, you exhibit a finite set SS and show that ∣S∣=A|S| = A by one counting argument and ∣S∣=B|S| = B by another. In a bijective proof, you construct a bijection f:X→Yf: X \to Y between finite sets with ∣X∣=A|X| = A and ∣Y∣=B|Y| = B.

Worked Example

Problem: Give a combinatorial proof that k(nk)=n(n−1k−1)k\binom{n}{k} = n\binom{n-1}{k-1} for all integers 1≤k≤n1 \le k \le n. Then check the identity for n=5n = 5 people and committees of k=3k = 3.
Step 1: Choose a set to count. Let SS be the set of ways to pick a kk-person committee from nn people and name one committee member as chair. Count SS committee-first. There are (nk)\binom{n}{k} ways to choose the committee, then kk ways to choose its chair.
∣S∣=(nk)⋅k|S| = \binom{n}{k} \cdot k
Step 2: Count the same set chair-first. There are nn ways to pick the chair from everyone. The other k−1k-1 members then come from the remaining n−1n-1 people. Each chaired committee arises exactly once in each count.
∣S∣=n⋅(n−1k−1)|S| = n \cdot \binom{n-1}{k-1}
Step 3: Both expressions equal ∣S∣|S|, so they are equal to each other. As a check with n=5n = 5 and k=3k = 3, both sides give 30.
3(53)=3⋅10=30,5(42)=5⋅6=303\binom{5}{3} = 3 \cdot 10 = 30, \qquad 5\binom{4}{2} = 5 \cdot 6 = 30
Answer: Both sides count the chaired committees of size kk chosen from nn people, so k(nk)=n(n−1k−1)k\binom{n}{k} = n\binom{n-1}{k-1}. For n=5n = 5 and k=3k = 3, each side equals 30.

Why It Matters

Combinatorial proofs are standard in college combinatorics and discrete math courses, where you prove binomial identities such as Pascal's rule or ∑k(nk)=2n\sum_k \binom{n}{k} = 2^n. They often explain why an identity is true, while an algebraic proof only confirms that it is. Computer science students use the same double-counting idea to analyze algorithms and count graph edges, as in the handshake lemma.

Common Mistakes

Mistake: Counting two slightly different sets on the two sides. For example, the left side counts committees with a chair, but the right side quietly counts ordered lists of members.
Correction: Define the set SS precisely before counting. Then confirm that each count produces every element of SS exactly once, with no overcounting and no omissions.

Related Terms

  • Discrete Mathematics — Field where counting proofs are a core technique
  • Proof — General idea of a proof that counting arguments specialize
  • Direct Proof — Alternative proof style that derives the identity algebraically, step by step
  • Combinatorics — Branch of math whose counting methods this proof uses