Discrete Math · Undergraduate
Combinatorial Proofs and Binomial Coefficient Identities
Quick answer
A combinatorial proof shows that two expressions are equal by explaining how each one counts the same collection. The binomial coefficient C(n, k) counts the k-element subsets of an n-element set, which makes many identities transparent. Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k) splits subsets by whether they contain one chosen element. Counting all subsets gives the row sum 2ⁿ, and choosing a committee and its chair two ways gives k·C(n, k) = n·C(n − 1, k − 1).
What you'll learn
- Interpret C(n, k) as a count of subsets
- Prove an identity by counting one set in two ways
- Prove Pascal's rule, the row sum and the committee–chair identity
- Use Vandermonde's identity and the hockey stick identity
Counting one thing two ways
The binomial coefficient counts the ways to choose elements from a set of . A combinatorial proof of an identity describes one collection of objects and counts it twice, once in the way the left side counts and once as the right side does. Since both count the same thing, they are equal.
| Row of Pascal’s triangle | Sum | |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 1 | 2 |
| 2 | 1 2 1 | 4 |
| 3 | 1 3 3 1 | 8 |
| 4 | 1 4 6 4 1 | 16 |
| 5 | 1 5 10 10 5 1 | 32 |
Why double counting proves Pascal’s rule
Take a set of people and single out one of them, Pat. Every group of either includes Pat or does not.
- Groups with Pat: choose the other from the remaining : .
- Groups without Pat: choose all from the remaining : .
Every group falls in exactly one case, so the two counts add up to all groups: . That is the rule that builds each row of Pascal’s triangle from the one above. No factorials were needed.
Worked examples
Common mistakes
Practice problems
-
Give a combinatorial reason that .
Answer
Choosing the elements to include is the same as choosing the to leave out.
Full solution
Each -subset matches exactly one -subset, its complement.
-
Verify Pascal’s rule for .
Answer
Full solution
and .
-
Prove using Vandermonde’s identity, and check .
Answer
Set and , and use ; for , .
Full solution
Choosing people from women and men, with women, gives ways.
-
Check the hockey stick identity .
Answer
Full solution
.
-
Prove the hockey stick identity combinatorially.
Answer
Sort the -subsets of by their largest element.
Full solution
If the largest element is , the other come from : ways. Adding over from to counts every subset once.
-
How many subsets of a -element set have an even number of elements?
Answer
Full solution
Pair subsets by adding or removing one fixed element; each pair has one even and one odd subset, so half of the are even.
-
Use the committee–chair identity to find .
Answer
Full solution
: choose a chair, then any subset of the others.
-
A student “proves” the row sum by checking . What is missing?
Answer
An argument for every , such as counting subsets two ways.
Full solution
Cases can suggest an identity but cannot prove it for all ; the double count does.
Frequently asked questions
What is a combinatorial proof?
A proof that two expressions are equal because both count the same set of objects, each in its own way.
How is Pascal's rule proved combinatorially?
Fix one element x of an n-element set. A k-subset either contains x (choose the other k − 1 from n − 1) or does not (choose all k from n − 1). So C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Why do the numbers in row n of Pascal's triangle add up to 2ⁿ?
Both sides count all subsets of an n-element set: by size on the left, and by deciding in or out for each element on the right.
What is Vandermonde's identity?
C(m + n, r) = Σₖ C(m, k)C(n, r − k): choose r people from m women and n men, sorted by how many women are chosen.
What is the hockey stick identity?
C(k, k) + C(k + 1, k) + ⋯ + C(n, k) = C(n + 1, k + 1). In Pascal's triangle, a diagonal run adds up to the entry diagonally below its end.