math.wiki
Logic, proof and discrete math › Proof techniques › Combinatorial proof: counting one set two ways
Open on the map
Discrete Mathematics and Proof

Combinatorial proof: counting one set two ways

Two expressions give the same number every time you test them. How can you see why they must agree, without pushing symbols around?

You need
The binomial theoremAlgebra 2Pascal's triangleAlgebra 2
Where you are 14 in Proof techniques
Logic, proof and discrete math6
Proof techniques14
▴ 9 aboveProof by contrapositionThe pigeonhole principleProof by contradiction
Combinatorial proof: counting one set two ways
Proof by induction3

Why this exists

An identity among binomial coefficients can be checked by algebra, writing each side with factorials and simplifying. That proves it but rarely shows why it holds, and for a sum such as \sum_k k(n - k)\binom{n}{k}^2 the algebra is long. If one collection of objects is counted in two ways, the two answers are the same number, however different they look on paper. Pascal’s rule was proved this way, and so were the row sum 2^n and the diagonal sum. This lesson makes the method explicit and adds its second form: matching two collections one to one.

Definition

This lesson takes two days. Day 1 is double counting (Examples 1 to 4); Day 2 is bijective proof (Examples 5 to 7).

Throughout, \lvert S \rvert is the number of members of a finite set S, and \binom{n}{k} is the number of k-element subsets of an n-element set (Combinations), taken as 0 when k < 0 or k > n.

A combinatorial proof of an identity A = B, where both sides are counts (nonnegative integers) for every allowed value of the variables, is a proof of one of two kinds.

  • Double counting. Name one finite set S. Show by one way of counting that \lvert S \rvert = A, and by another that \lvert S \rvert = B.
  • Bijective proof. Name finite sets S and T with \lvert S \rvert = A and \lvert T \rvert = B, and give a bijection f : S \to T.

Each count must count every member exactly once. Usually this means sorting S into cases that do not overlap and together cover S, then counting each case in stages by the multiplication principle.

Intuition

2 2 2 2 2 2 3 3 3 3 clubs students
Figure 1Rows are students, columns are clubs. Counted by rows the dots number 6 \cdot 2 = 12; counted by columns, 4 \cdot 3 = 12.

Figure 1 records which of six students belong to which of four clubs. Counting the dots by rows gives 2 + 2 + 2 + 2 + 2 + 2 = 12, and by columns 3 + 3 + 3 + 3 = 12. Nobody needs to check that these agree: they are the same twelve dots. Every double-counting proof is this picture with a cleverer choice of rows and columns, and one side of the identity usually suggests what to count: \binom{2n}{n} suggests choosing n from 2n, 2^n suggests subsets, and a factor k in front of \binom{n}{k} suggests one special member of a k-element set.

A bijective proof pairs off two sets instead. Taking complements pairs the k-element subsets with the (n - k)-element subsets, proving \binom{n}{k} = \binom{n}{n - k} (Combinations); switching one fixed element in or out pairs the subsets of even size with those of odd size (Pascal's triangle, Example 6).

Results

1. Double counting. If a finite set is counted in two ways, giving A and B, then A = B.

2. Counting pairs two ways. Let X and Y be finite sets and R a set of pairs (x, y) with x \in X and y \in Y. For x \in X let r(x) be the number of pairs in R with first entry x, and for y \in Y let c(y) be the number with second entry y. Then

\sum_{x \in X} r(x) = \lvert R \rvert = \sum_{y \in Y} c(y).

In particular, if every x is in exactly a pairs and every y in exactly b, then a\lvert X \rvert = b\lvert Y \rvert.

3. Bijection. If f : S \to T is a bijection between finite sets, then \lvert S \rvert = \lvert T \rvert.

Why it is true

Result 1. A finite set has one number of members, and each correct way of counting finds it. The work in a combinatorial proof is showing each way is correct: its cases do not overlap, they miss nothing, and each case count is right.

Result 2. Proof. For each x \in X, let R_x be the set of pairs in R with first entry x. Every pair has exactly one first entry, so the sets R_x do not overlap and together make up R. Adding their sizes gives \lvert R \rvert = \sum_x r(x). Sorting by second entry instead gives \lvert R \rvert = \sum_y c(y). If every r(x) = a, the first sum is a\lvert X \rvert; if every c(y) = b, the second is b\lvert Y \rvert. \square

Result 3. This is Result 1 of Matching two sets one to one, not proved again here.

Worked examples

Example 1

Day 1: clubs counted two ways

Sindri is planning clubs for 30 students. Each student is to join exactly 4 clubs, and each club is to have exactly 8 members. How many clubs must there be? Could 25 students instead each join exactly 3 clubs of exactly 6 members?

Solution

Count the pairs (student, club) in which the student belongs to the club. Sorted by student, each of the 30 students is in 4 pairs, so there are 30 \cdot 4 = 120 pairs. Sorted by club, each club is in 8 pairs, so with c clubs there are 8c pairs. By Result 2, 8c = 120, so c = 15. Any plan meeting the conditions has exactly 15 clubs.

The second plan gives 25 \cdot 3 = 75 pairs counted by student and 6c counted by club. No integer c has 6c = 75, since 75 is odd and 6c is even. So the second plan is impossible.

Example 2

Day 1: powers of 2 by the largest element

Prove that for every positive integer n,

1 + 2 + 4 + \cdots + 2^{n - 1} = 2^n - 1.
Solution

Proof. Let S be the set of nonempty subsets of \{1, 2, \ldots, n\}. Of its 2^n subsets (Pascal's triangle) only the empty set is left out, so \lvert S \rvert = 2^n - 1.

Now sort the members of S by their largest element. Each nonempty subset has exactly one largest element m, with 1 \le m \le n, so the cases do not overlap and cover S. A subset with largest element m is \{m\} \cup Y, where Y is any subset of \{1, \ldots, m - 1\}, and different choices of Y give different subsets. There are 2^{m - 1} choices of Y. Adding over m = 1, \ldots, n gives \lvert S \rvert = 2^0 + 2^1 + \cdots + 2^{n - 1}. The two counts are equal. \square

For n = 4: the subsets of \{1, 2, 3, 4\} with largest element 1, 2, 3, 4 number 1, 2, 4, 8, and 1 + 2 + 4 + 8 = 15 = 2^4 - 1.

Example 3

Day 1: a club with a president and a vice president

Prove that for every integer n \ge 2,

\sum_{k=2}^{n} k(k - 1)\binom{n}{k} = n(n - 1)2^{n - 2}.
Solution

The factor k(k - 1) is the number of ways to pick, from k people, a president and then a different vice president.

Proof. From a group of n people, form a club (any subset of the group) and choose from its members a president and a vice president, who must be different people. Let S be the set of all such choices of (club, president, vice president).

First count: sort by the size k of the club. A club of size k can be chosen in \binom{n}{k} ways, then the president in k ways and the vice president in k - 1 ways. A club with fewer than 2 members cannot have two officers, so k runs from 2 to n, and \lvert S \rvert is the left side.

Second count: choose the officers first. The president is any of the n people and the vice president any of the other n - 1. Each of the remaining n - 2 people is in the club or not, independently, which gives 2^{n - 2} ways to finish the club. So \lvert S \rvert = n(n - 1)2^{n - 2}. \square

For n = 4 the terms on the left are 12, 24 and 12, adding to 48, and the right side is 4 \cdot 3 \cdot 4 = 48.

Example 4

Day 1: a panel from two groups, with two officers

Prove that for every integer n \ge 2,

\sum_{k=1}^{n - 1} k(n - k)\binom{n}{k}^2 = n^2\binom{2n - 2}{n - 2}.
Solution

Read \binom{n}{k}^2 as \binom{n}{k}\binom{n}{n - k}: k from one group of n and n - k from another, with one officer from each part.

Proof. A school has n teachers and n parents. Count the ways to choose a panel of n of these 2n people together with a chair, who must be a teacher on the panel, and a secretary, who must be a parent on the panel.

Choosing the officers first: the chair is any of the n teachers and the secretary any of the n parents. The other n - 2 panel members are any n - 2 of the remaining 2n - 2 people, in \binom{2n - 2}{n - 2} ways. This gives the right side.

Sorting by the number k of teachers on the panel: the k teachers can be chosen in \binom{n}{k} ways and the chair among them in k ways; the other n - k members come from the parents in \binom{n}{n - k} ways and the secretary among them in n - k ways. Since \binom{n}{n - k} = \binom{n}{k} (Combinations), case k contributes k(n - k)\binom{n}{k}^2. Each officer needs a member of their group, so k runs from 1 to n - 1; these cases do not overlap and cover every choice. This gives the left side. \square

For n = 3: 1 \cdot 2 \cdot 9 + 2 \cdot 1 \cdot 9 = 36 and 9\binom{4}{1} = 36. Dropping both officers, the same sorting proves \sum_k \binom{n}{k}^2 = \binom{2n}{n}, which The binomial theorem proved by algebra.

Example 5

Day 2: subset sums above and below the middle

The subsets of \{1, 2, \ldots, 8\} have sums from 0 (the empty set) to 36. Prove that exactly as many subsets have a sum less than 18 as have a sum greater than 18. Given that 14 subsets have sum exactly 18, find how many have a sum less than 18.

Solution

Proof. Let L be the set of subsets with sum less than 18, and G the set with sum greater than 18. Send a subset X to its complement X^c = \{1, \ldots, 8\} \setminus X. Each number from 1 to 8 is in exactly one of X and X^c, so their sums add to 1 + 2 + \cdots + 8 = 36: the sum of X^c is 36 minus the sum of X. If the sum of X is less than 18, the sum of X^c is greater than 36 - 18 = 18. So X \mapsto X^c maps L into G, and in the same way G into L. Taking the complement twice gives X back, so the two maps are inverse to each other, and a map with an inverse is a bijection (Composing functions between sets, and when an inverse exists). By Result 3, \lvert L \rvert = \lvert G \rvert. \square

There are 2^8 = 256 subsets in all. Removing the 14 with sum 18 leaves 242, split equally between L and G, so \lvert L \rvert = 121.

Example 6

Day 2: subsets with no two consecutive numbers

Prove that for integers n \ge 1 and k \ge 1, the number of k-element subsets of \{1, 2, \ldots, n\} that contain no two consecutive integers is \binom{n - k + 1}{k}. How many 3-element subsets of \{1, \ldots, 8\} have no two consecutive integers?

Solution

Proof. Let S be the set of k-element subsets of \{1, \ldots, n\} with no two consecutive integers, and T the set of all k-element subsets of \{1, \ldots, n - k + 1\}. Write a member of S in increasing order, a_1 < a_2 < \cdots < a_k; no two consecutive means a_{i+1} - a_i \ge 2. Close up the gaps by subtracting i - 1 from the ith smallest member:

\begin{aligned} f(\{a_1, \ldots, a_k\}) &= \{b_1, \ldots, b_k\}, \\ b_i &= a_i - (i - 1). \end{aligned}

Then b_{i+1} - b_i = a_{i+1} - a_i - 1 \ge 1, so the b_i are k different numbers in increasing order, with b_1 = a_1 \ge 1 and b_k = a_k - k + 1 \le n - k + 1. So f maps S into T.

Going back, for b_1 < \cdots < b_k in \{1, \ldots, n - k + 1\} put a_i = b_i + (i - 1). Then a_{i+1} - a_i = b_{i+1} - b_i + 1 \ge 2, a_1 = b_1 \ge 1 and a_k = b_k + k - 1 \le n, so the result lies in S. The two maps undo each other, so f is a bijection and \lvert S \rvert = \lvert T \rvert = \binom{n - k + 1}{k}. \square

With n = 8 and k = 3 there are \binom{6}{3} = 20 such subsets; for instance \{2, 5, 8\} is sent to \{2, 4, 6\}, and \{1, 3, 5\} to \{1, 2, 3\}. When n - k + 1 < k the count is 0, which is right: k members with gaps of at least 2 need a_k \ge 2k - 1 > n.

Example 7

Day 2: lattice paths that touch a line

A lattice path from (0, 0) to (6, 4) takes 10 unit steps, each right (R, adding 1 to x) or up (U, adding 1 to y). How many of these paths touch the line y = x + 2, and how many stay below it all the way?

Solution

A path is a list of 10 steps of which 4 are U, so choosing the places of the U steps gives \binom{10}{4} = 210 paths. Call a path bad if it touches the line.

Reflection in the line y = x + 2 sends (x, y) to (y - 2, x + 2). It sends lattice points to lattice points, leaves every point of the line where it is, and swaps R steps with U steps.

(0, 0) (6, 4) (2, 8)
y = x + 2
Figure 2The solid path to (6, 4) first touches y = x + 2 at (1, 3), the large dot. Reflecting the rest of it in the line gives the dashed ending, and a path to (2, 8).

Proof that there are 45 bad paths. Take a bad path and let P be the first point where it touches the line. Keep the part up to P and reflect the part after P. The reflected part starts at P, which stays put, and ends at the reflection of (6, 4), which is (4 - 2, 6 + 2) = (2, 8). The result is a lattice path from (0, 0) to (2, 8) (Figure 2).

Conversely, take any lattice path from (0, 0) to (2, 8). Along it, y - x starts at 0, ends at 6, and changes by exactly 1 at each step, so it equals 2 somewhere: the path touches the line. Reflect its part after the first touch. The part before is unchanged, so the first touch is the same point, and the result is a bad path to (6, 4).

Both operations keep the first touching point and everything before it, and reflecting twice returns the original, so they undo each other. Bad paths are therefore matched one to one with the paths to (2, 8), which have 2 right steps among 10: there are \binom{10}{2} = 45. \square

So 45 paths touch the line and 210 - 45 = 165 stay strictly below it, with y \le x + 1 at every point. No path crosses the line without touching it, because y - x moves by 1 at a time.

Boundaries

  • Finite sets. Result 1 needs a finite set. For infinite sets a bijection still means “the same size” (Matching two sets one to one), but sizes no longer subtract like numbers: \mathbb{N} splits into the even and the odd natural numbers, each the same size as the whole. A step like “remove 14, then halve” needs finite sets.
  • Each count must be exact. The cases must not overlap and must miss nothing. A way of counting that meets every object m times, as ordered choices do for unordered ones, must be divided by m, and m must be the same for every object.
  • A bijection needs both halves. An injective map that is not surjective proves only \lvert S \rvert \le \lvert T \rvert (Exercise 17). Each map must land in the right set, as the range checks in Example 6 show.
  • The range of the variables. The identity is proved only where the count makes sense: Example 3 needs n \ge 2, and switching a fixed element needs a nonempty set (for n = 0 the one subset, \varnothing, has even size). A side with subtraction must first be read as a count, such as “how many are left”.
  • Finding the set is insight. Not every identity has a known counting proof; algebra or induction is still a complete proof.

Where this goes next

The two groups of Example 4 lead to the general rule for choosing from two groups at once, known as Vandermonde’s identity. Reflecting in the line y = x + 1 instead counts the paths from (0, 0) to (n, n) that never rise above the diagonal, the Catalan numbers. Counting pairs two ways returns in graph theory, linking the degrees of a graph to its number of edges (Degree, the handshake lemma and complete graphs). And sorting by a last feature, as in Example 2, is how recurrences are set up from counting problems.

Exercises

Day 1: counting pairs two ways

  1. A cookbook has 12 dishes. Each dish uses exactly 5 spices from the cookbook’s spice list, and each spice on the list is used in exactly 4 dishes. How many spices are on the list?
  2. A configuration has 13 points and some lines. Each line contains exactly 4 of the points, each point lies on exactly 4 lines, and every two points lie on exactly one common line. Find the number of lines twice: by counting (point, line) pairs, and by counting (pair of points, line) pairs.
  3. Can 14 judges each read exactly 3 essays, with each essay read by exactly 4 judges? Prove your answer.
  4. Use Example 4 to find \sum_{k=1}^{4} k(5 - k)\binom{5}{k}^2, and check the value by adding the four terms.

Day 1: identities by double counting

  1. Prove that for nonnegative integers j, k, n with j + k \le n, \binom{n}{k}\binom{n - k}{j} = \binom{n}{j}\binom{n - j}{k}. (Choose a team of k players and, from the rest, j referees.)
  2. Prove that for every integer n \ge 2, \sum_{k=1}^{n} k^2\binom{n}{k} = n(n + 1)2^{n - 2}. (In Example 3, let one person hold both offices if you like.)
  3. Prove that for every positive integer n, \sum_{j=1}^{n} \binom{n}{j}\binom{n}{j - 1} = \binom{2n}{n + 1}.

Day 2: counting through a bijection

  1. How many 3-element subsets of \{1, 2, \ldots, 12\} contain no two consecutive integers?
  2. How many subsets of \{1, 2, \ldots, 6\}, of any size and including the empty set, contain no two consecutive integers?
  3. How many lattice paths from (0, 0) to (5, 5) never touch the line y = x + 2?
  4. How many subsets of \{1, 2, \ldots, 10\} have a sum of at most 27?

Day 2: bijective proofs

  1. For n \ge 2, prove that exactly \displaystyle \frac{n!}{2} of the arrangements of 1, 2, \ldots, n in a row have a first entry smaller than the second.
  2. Prove that for 1 \le k \le n, the k-element subsets of \{1, \ldots, n\} with sum s are exactly as many as those with sum k(n + 1) - s.
  3. Prove that for n \ge 1, exactly 2^{n - 1} subsets of \{1, \ldots, n\} have an even sum. (The empty set has sum 0.)

Reasoning

  1. Prove that \sum_{m=1}^{n} m \cdot m! = (n + 1)! - 1 for every positive integer n, by counting the arrangements of 1, 2, \ldots, n + 1 in a row other than 1, 2, \ldots, n + 1 itself, sorted by the first position whose entry differs from the position’s number.
  2. Matteus argues that \{a_1, \ldots, a_k\} \mapsto \{a_1 - 1, a_2 - 2, \ldots, a_k - k\}, with a_1 < \cdots < a_k, is a bijection from the k-element subsets of \{1, \ldots, n\} with no two consecutive integers to the k-element subsets of \{1, \ldots, n - k\}, so that there are \binom{n - k}{k} of them. Find the flaw, and test the claim with n = 4 and k = 2.
  3. For 0 \le k < n, let f send each k-element subset X of \{1, \ldots, n\} to X \cup \{n + 1\}, a (k + 1)-element subset of \{1, \ldots, n + 1\}. Show that f is injective but not surjective. What does f prove, and which subsets does it miss?
  4. Prove the identity of Exercise 5 again, from \displaystyle \binom{n}{r} = \frac{n!}{r!(n - r)!}. What does the counting proof tell you that the algebra does not?
Answers
  1. 15 spices. Counting (dish, spice) pairs: 12 \cdot 5 = 60 by dishes and 4s by spices, so 4s = 60 and s = 15.
  2. 13 lines both ways. With L lines, (point, line) pairs number 13 \cdot 4 = 52 by points and 4L by lines, so L = 13. Each of the \binom{13}{2} = 78 pairs of points lies on one line, and each line holds \binom{4}{2} = 6 pairs, so 6L = 78 and again L = 13.
  3. No. Counting (judge, essay) pairs gives 14 \cdot 3 = 42 by judges and 4e by essays, where e is the number of essays. But 42 = 4 \cdot 10 + 2 is not a multiple of 4.
  4. 25\binom{8}{3} = 25 \cdot 56 = 1400. The terms are 100 + 600 + 600 + 100 = 1400.
  5. Count the ways to choose, from n people, a team of k and a separate group of j referees. Team first: \binom{n}{k} teams, then \binom{n - k}{j} referee groups from the others. Referees first: \binom{n}{j}, then \binom{n - j}{k} teams. Both count the same choices. \square
  6. Count (club, president, vice president) with both officers in the club, possibly the same person. By club size: k^2\binom{n}{k} for size k, the left side. Officers first: one person in both roles gives n \cdot 2^{n - 1}; two different people give n(n - 1)2^{n - 2}, as in Example 3. Factoring n2^{n - 2} out of the total leaves 2 + (n - 1) = n + 1. \square
  7. From n teachers and n parents choose n + 1 people: \binom{2n}{n + 1} ways. Sorted by the number j of teachers: \binom{n}{j}\binom{n}{n + 1 - j}, where j \ge 1 because at most n are parents. By symmetry \binom{n}{n + 1 - j} = \binom{n}{j - 1}, which gives the left side. \square
  8. \binom{12 - 3 + 1}{3} = \binom{10}{3} = 120, by Example 6.
  9. 21. By size k = 0, 1, 2, 3, Example 6 gives \binom{7}{0} + \binom{6}{1} + \binom{5}{2} + \binom{4}{3}, and this is 1 + 6 + 10 + 4 = 21; for k \ge 4, \binom{7 - k}{k} = 0.
  10. 132. All paths: \binom{10}{5} = 252. Reflecting (5, 5) in y = x + 2 gives (3, 7), so as in Example 7 the touching paths match the paths to (3, 7): \binom{10}{3} = 120. Then 252 - 120 = 132.
  11. 512. The numbers 1 to 10 add to 55, so the complement sends a sum s to 55 - s and matches the subsets with sum at most 27 with those with sum at least 28. Every subset is in one of the two groups, so each holds half of 2^{10} = 1024.
  12. Let A be the arrangements with first entry smaller than the second, and B those with it larger; every arrangement is in exactly one. Swapping the first two entries maps A to B and B to A, and swapping twice changes nothing, so it is a bijection. With \lvert A \rvert + \lvert B \rvert = n! (Arrangements and factorials), \displaystyle \lvert A \rvert = \frac{n!}{2}. \square
  13. Send X to X' = \{n + 1 - a : a \in X\}. Different members a give different values n + 1 - a, all in \{1, \ldots, n\}, so X' is again a k-element subset, and if X has sum s then X' has sum k(n + 1) - s. Applying the map twice gives X back, since n + 1 - (n + 1 - a) = a, so it is a bijection from the subsets with sum s to those with sum k(n + 1) - s (Composing functions between sets, and when an inverse exists). By Result 3 the counts agree. \square
  14. Put 1 in a subset if it is absent and take it out if present. The sum changes by 1, so its parity flips, and doing it twice changes nothing. This bijection matches even-sum subsets with odd-sum ones, so each kind is half of 2^n, that is, 2^{n - 1}. \square
  15. There are (n + 1)! - 1 such arrangements. If position i is the first whose entry is not i, positions 1 to i - 1 hold 1 to i - 1, so position i holds one of i + 1, \ldots, n + 1: n + 1 - i choices. The other entries fill the remaining places in (n + 1 - i)! orders. Here i \le n, since fixing the first n places fixes the last. With m = n + 1 - i the cases give \sum_{m=1}^{n} m \cdot m!. \square
  16. A subset containing 1 is sent to a set containing 1 - 1 = 0, outside \{1, \ldots, n - k\}. The images lie in \{0, \ldots, n - k\}, which has n - k + 1 members, giving \binom{n - k + 1}{k} as in Example 6. For n = 4, k = 2 the subsets are \{1, 3\}, \{1, 4\}, \{2, 4\}: three, while \binom{2}{2} = 1.
  17. X is recovered as f(X) \setminus \{n + 1\}, so f is injective. Since k + 1 \le n, the set \{1, \ldots, k + 1\} is not an image. So f proves \binom{n}{k} \le \binom{n + 1}{k + 1}, strictly. It misses exactly the \binom{n}{k + 1} subsets of size k + 1 without n + 1; adding them back gives Pascal’s rule.
  18. The left side is \displaystyle \frac{n!}{k!(n - k)!} \cdot \frac{(n - k)!}{j!(n - k - j)!}, which is \displaystyle \frac{n!}{k!\,j!\,(n - j - k)!}, and the right side simplifies to the same fraction with j and k swapped. The counting proof also shows what the common value counts (splits of n people into a team, referees and the rest), so the order of choosing cannot matter. \square
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0