You want to prove that C(n,k) = C(n, n−k). Which approach most directly reveals WHY the identity holds?
AExpand both sides using the factorial formula n!/(k!(n−k)!) and simplify algebraically
BMap each k-element subset of {1,...,n} to its complement — the remaining (n−k) elements — and observe this is a bijection
CUse double-counting: count the number of ways to choose a k-subset by two different methods
DArgue by symmetry that choosing k items is equivalent to choosing n−k items by inspection
The bijection proof — sending each k-subset to its complement — is a function that pairs every k-element subset with exactly one (n−k)-element subset, with no leftovers. This is a bijection, so the two collections must be the same size. The algebraic proof shows the identity holds; the bijection proof reveals WHY — the two sets are genuinely the same collection of objects, viewed from opposite sides. Option 2 (double-counting) would count one set in two ways; bijection establishes a correspondence between two different sets.
Question 2 Multiple Choice
Two finite sets A and B are claimed to have the same cardinality. Which of the following is sufficient proof?
ACounting |A| and |B| separately and confirming they are equal
BShowing that A and B contain the same types of mathematical objects
CExhibiting a surjective function from A to B
DExhibiting a bijection between A and B
A bijection — injective and surjective — guarantees every element of A pairs with exactly one element of B with no element of B unpaired. This is sufficient proof of equal cardinality regardless of whether you have counted either set. Option C (surjection alone) is not sufficient: a surjection from A to B can exist even when |A| > |B|. Option A also works but misses the point — bijection proves equality without requiring either count.
Question 3 True / False
A bijection between two sets proves they have the same cardinality even if neither set has been explicitly counted.
TTrue
FFalse
Answer: True
This is exactly the power of the bijection principle. The pairing itself is the proof — like pairing left and right socks to confirm they are equal in number without counting them. In combinatorics, this allows proving equalities between formulas that look different by constructing a structural correspondence rather than evaluating both sides.
Question 4 True / False
The bijection counting principle and the double-counting principle are essentially the same technique, since both involve pairing up elements.
TTrue
FFalse
Answer: False
Double-counting counts a single set in two different ways, producing an equation between two expressions that count the same thing. The bijection principle constructs a correspondence between two *different* sets to prove they have the same size. The intellectual move is different: double-counting asks 'how many ways can I count this one set?'; bijection asks 'is this collection secretly the same size as that one?'
Question 5 Short Answer
Why is a bijection proof of a combinatorial identity more illuminating than an algebraic proof of the same identity?
Think about your answer, then reveal below.
Model answer: An algebraic proof shows that two formulas simplify to the same number but does not explain why the underlying objects correspond. A bijection proof exhibits an explicit pairing between the objects being counted, revealing a structural reason for the equality — the two sets are genuinely in one-to-one correspondence. This gives insight into the combinatorial meaning of the identity, not just its numerical truth.
The classic example is C(n,k) = C(n, n−k): the algebraic proof is mechanical cancellation of factorials, but the bijection proof shows that choosing k items is the same act as choosing which (n−k) items to leave out. The bijection makes the why visible.