1
Double counting needs one set and two classifications
Both expressions must count the same objects. Naming those objects precisely is where the proof is won.
Lesson · Combinatorics and Counting · Technique
Combinatorial Proof
Two techniques that prove identities without algebra: count a single set in two ways, or construct a bijection between two sets. Both explain the identity as well as establishing it.
DOUBLE COUNTING one set, two counts ⟹ the counts are equal
BIJECTION a pairing between two sets ⟹ equal sizes
Both give WHY, which algebra does not.
State the objects first. Everything else follows.
Two techniques
Core ideas
What this lesson establishes
An algebraic proof confirms an identity. A combinatorial proof explains it, and is usually shorter.
2
A bijection needs an explicit map
Describe the map, show it is injective, show it is surjective. "Clearly there is a correspondence" is not a proof.
3
The explanation is the value
Σ k·C(n,k) = n·2ⁿ⁻¹ proved by counting tells you the n is a chair and the 2ⁿ⁻¹ is everyone else. The algebra tells you nothing.
The material
Two techniques
Double counting and bijection, with several identities each.
Double counting
Theorem · The method
To prove A = B, find a set S and show that counting S one way gives A and another way gives B. Since S has one size, A = B.
Example · Handshakes
In any graph, Σ_v deg(v) = 2|E|. Count the incidences — pairs (vertex, edge at that vertex). By vertex: each contributes its degree. By edge: each has two endpoints. “Degree and the Handshake Theorem” in Graphs and Trees opens with this.
Example · Pascal's rule, again
C(n,k) = C(n−1,k−1) + C(n−1,k): count k-subsets by whether they contain a fixed element. One set, two classifications.
Example · Vandermonde
C(m+n,r) = Σ_k C(m,k)C(n,r−k): count r-subsets of a set split into groups of m and n, classified by how many come from the first group.
Vandermonde with m = n = r reads C(2n, n) = Σ_k C(n,k)·C(n,n−k), and the symmetry C(n,n−k) = C(n,k) turns it into Σ_k C(n,k)² = C(2n,n): the n-subsets of a 2n-set, classified by how many come from the first half. The square is two halves of the same size making the same kind of choice. An identity that looks as if it needs algebra is often a known double count in disguise, and recognising which is the skill.
Bijective proof
Theorem · The method
To prove |A| = |B|, construct an explicit bijection f : A → B. The criteria of “Injective, Surjective, Bijective”, in Sets, Relations, and Functions, apply: injective and surjective, both argued.
Example · Symmetry of binomial coefficients
C(n,k) = C(n,n−k) via complementation: send each k-subset to its complement. It is its own inverse, hence a bijection.
Example · Subsets and bit strings
|P(S)| = 2ⁿ via the indicator map: send a subset to the string with a 1 in position i exactly when the ith element is in. Injective because a subset is determined by its members; surjective because every string names a subset.
Example · Compositions
The number of ways to write n as an ordered sum of positive integers is 2ⁿ⁻¹. Bijection: write n as n ones separated by n−1 gaps, and choose which gaps to cut. Each subset of gaps gives one composition, and conversely.
When to use which
- The identity has a sum on one side: double count, classifying by whatever the summation index measures.
- The identity says two counts are equal with no sum: look for a bijection.
- The identity has alternating signs: neither directly. Look for a sign-reversing involution — a pairing that cancels most terms — or use inclusion and exclusion.
A word on rigour. A combinatorial proof is a proof, not an intuition. The obligations are precise: for double counting, say what the objects are and check both classifications are exhaustive and disjoint; for a bijection, define the map and argue both directions.
Interactive
Pascal's triangle
Identities highlighted and checked
Method
Constructing a combinatorial proof
Name the objects before anything else.
1
Decide what each side counts
Read the expressions as counts. n·2ⁿ⁻¹ counts a choice followed by independent decisions; Σ k·C(n,k) counts a set and a distinguished element.
2
Find one set both sides could count
Usually the more complicated side names it. Write the objects down explicitly.
3
Justify each count
Say which rule you are applying and check the classification is disjoint and exhaustive.
4
For a bijection, define the map both ways
Give f and give its inverse. Producing the inverse is the cleanest way to establish bijectivity.
Combinatorial proof
Score 0 / 0Choose the answer you can justify.
Prove C(n,k)·C(k,j) = C(n,j)·C(n−j, k−j)
Count pairs (a k-subset, a j-subset of it) two ways.
OBJECTS pairs (A, B) with B ⊆ A ⊆ S, |S| = n, |A| = k, |B| = j.
COUNT 1 — choose A first:
A: C(n,k) ways. Then B ⊆ A with |B| = j: C(k,j) ways.
Total C(n,k)·C(k,j).
COUNT 2 — choose B first:
B: C(n,j) ways. Then the other k−j elements of A come from
the n−j elements outside B: C(n−j, k−j) ways.
Total C(n,j)·C(n−j, k−j).
One set, two counts ⟹ the expressions are equal. ∎
The algebraic proof expands four factorial expressions and cancels. It is correct and it leaves you knowing nothing. The counting proof says the identity is true because the inner set can be chosen before or after the outer one, which is a fact you can carry to the next problem.
Common mistakes
1
Not saying what the objects are"Both sides count the same thing" is not a proof until the thing is named. The naming is most of the work.
2
A classification with a gap or an overlapThe same discipline as a proof by cases. Every object in exactly one class, and say why.
3
Asserting a bijection without defining it"There is an obvious correspondence" is where errors hide. Write the map and its inverse.
Check your understanding
✓
Finish when you prefer the counting proof.
Two proofs, one of each kind. First, “The Binomial Theorem” obtained Σ_k 2ᵏ·C(n,k) = 3ⁿ by substitution; prove it by double counting instead, and say what a single object being counted is — a pair A ⊆ B ⊆ S, or a function from S to a three-element set; either works. Second, prove that the k-subsets of {1, …, n} containing no two consecutive integers number C(n − k + 1, k), by a bijection: subtract i − 1 from the ith smallest element, write down the inverse, and check the map at n = 5, k = 2, where both sides are 6.
Note: Some identities have no known combinatorial proof, which is a genuine open kind of question: finding a bijection where only algebra is known is an active research activity, because the bijection carries information the algebra does not.