MATC44H3 Chap.10 Combinatorial Proofs by Double Counting
Combinatorial Proofs by Double Counting
Two kinds of proof for one identity
The week 2 lecture contrasts an algebraic proof of a counting identity, which expands binomial coefficients as factorials and may use induction, with a combinatorial proof, which finds a question that both sides answer.
The procedure is fixed: determine a question the identity answers, answer it in two different ways, and conclude that the answers are equal because they count the same thing.
The lecture's identities
Six identities are proved this way. Symmetry, C(n, k) = C(n, n − k), comes from choosing the toys to keep or the toys to discard.
The square n² is split by the number of 1s in an ordered pair and again by the larger entry of the pair, which gives the sum of the first n odd numbers. The sum of C(n, k) over k equals 2 to the n, counted with pretzel toppings that are each included or omitted. Choosing two people from m professors and n students gives C(m + n, 2) = C(m, 2) + C(n, 2) + mn.
Committees with a president give the sum of k · C(n, k) as n · 2 to the n − 1, and pizzas with n of 2n toppings give the sum of squares of C(n, k) as C(2n, n).
Reading the shape of an identity
The slides note that a plus sign usually signals a split into disjoint cases, and a sum over k usually signals classification by a size. A product signals stages chosen in turn.
Pascal's rule, scheduled with Pascal's triangle in week 4, follows the same pattern by asking whether one particular person is in a committee.
What this chapter covers
- 01
Algebraic versus combinatorial proof
- 02
The three-step double-counting procedure
- 03
Symmetry of binomial coefficients
- 04
Sums of binomial coefficients and subsets
- 05
Splitting ordered pairs by a maximum
- 06
Committees with a president
- 07
Pascal's rule by a special person
Worked example · free
Pairs chosen from n + 1 people
- 1Question: how many pairs can be chosen from n + 1 people, one of whom is Lee?
- 1Answer 1: C(n + 1, 2) by definition.
- 2Answer 2: pairs without Lee, C(n, 2), plus pairs with Lee, n, since Lee's partner is any of the others.
- 1Both answers count the same pairs, so the expressions are equal.
Key terms
- Double Counting
- Double counting is counting one set in two different ways and equating the results.
- Algebraic Proof
- An algebraic proof establishes an identity by manipulating formulas, such as factorial expressions, rather than by counting.
- Pascal's Rule
- Pascal's rule states that C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for 1 ≤ k ≤ n − 1.
- Symmetry Identity
- The symmetry identity states that C(n, k) = C(n, n − k), since keeping k objects means discarding n − k.
Combinatorial Proofs by Double Counting FAQ
How do I find the question for a combinatorial proof?
Start from the simpler side. A single binomial coefficient suggests choosing a committee or subset, a power of 2 suggests including or excluding each element, and n² suggests ordered pairs. Then read the other side for its split: a plus sign means disjoint cases and a sum over k means classifying by size.
Is an algebraic proof acceptable when a combinatorial proof is asked for?
If the question asks for a combinatorial proof, an algebraic proof does not answer it, even if it is correct. The lecture shows both kinds for the symmetry identity precisely to separate them. Read the instruction and give the kind of argument requested.
Why must the cases in my second count be disjoint?
The second count adds the cases, which is only valid by the addition principle when no object belongs to two cases. If the cases overlap, some objects are counted twice and the two answers no longer count the same set. Show that each object lands in exactly one case.
Can I check a combinatorial identity before proving it?
Yes, and you should. Substitute a small value such as n = 3 or n = 4 and compute both sides by hand. A mismatch means the identity has been misremembered or misread, which no proof can repair, while agreement gives confidence that the story you are building counts the right set.
Exam move
Write the six lecture identities and, beside each, the story and the split, without looking. Check each for n = 4 numerically. Then prove Pascal's rule and one identity of your own choosing combinatorially, stating the question, both answers and the conclusion as separate sentences.
Working through Combinatorial Proofs by Double Counting in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 Combinatorial Proofs by Double Counting question and get a clear, step-by-step explanation grounded in how MATC44H3 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
