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 (with nonnegative integers depending on parameters such as and ) uses one of two methods. In a double-counting proof, you exhibit a finite set and show that by one counting argument and by another. In a bijective proof, you construct a bijection between finite sets with and .
Worked Example
Problem: Give a combinatorial proof that for all integers . Then check the identity for people and committees of .
Step 1: Choose a set to count. Let be the set of ways to pick a -person committee from people and name one committee member as chair. Count committee-first. There are ways to choose the committee, then ways to choose its chair.
Step 2: Count the same set chair-first. There are ways to pick the chair from everyone. The other members then come from the remaining people. Each chaired committee arises exactly once in each count.
Step 3: Both expressions equal , so they are equal to each other. As a check with and , both sides give 30.
Answer: Both sides count the chaired committees of size chosen from people, so . For and , 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 . 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 precisely before counting. Then confirm that each count produces every element of exactly once, with no overcounting and no omissions.
