In the handshake problem, when you count 'each of n people shakes hands with n-1 others,' giving n(n-1) total, why must you divide by 2 to get the actual number of handshakes?
ABecause only half of the n people are initiating handshakes; the other half are receiving
BBecause each handshake involves exactly two people, so it was counted once from each participant's perspective — resulting in every handshake being tallied twice
CBecause n(n-1) counts ordered pairs of people, and you divide by 2 to convert to unordered pairs without double-counting
DBoth B and C describe the same underlying reason, just phrased differently
Options B and C are both accurate descriptions of the same mathematical fact, which is why D is correct. Each handshake has two participants; when you sum over people, you count from every participant's perspective, so each handshake appears in the sum exactly twice — once for each person involved. Dividing by 2 corrects for this. This is identical to saying n(n-1) counts ordered pairs (A shakes B's hand, B shakes A's hand) while handshakes are unordered — the same pair counted twice. The double counting identity is: n(n-1)/2 = C(n,2).
Question 2 Multiple Choice
Pascal's identity C(n-1, k-1) + C(n-1, k) = C(n, k) can be proved by double counting. What finite set is being counted in two different ways?
AThe number of ways to arrange k items from n in a specific order
BThe number of k-element subsets of an n-element set, split by whether a designated element (say, Alice) is in the subset or not
CThe total number of subsets of all sizes from an n-element set
DThe number of distinct pairs that can be formed from the remaining n-1 elements after removing one
The set being counted is: all k-element subsets of {1, 2, ..., n}. Method 1: there are C(n,k) such subsets by definition. Method 2: pick a distinguished element, say element n. Either n is in the subset (choose the remaining k-1 from {1,...,n-1}: C(n-1,k-1) ways) or n is not in the subset (choose all k from {1,...,n-1}: C(n-1,k) ways). Since every k-subset either contains n or doesn't, these cases partition the count: C(n-1,k-1) + C(n-1,k) = C(n,k). The identity follows by counting the same set two ways.
Question 3 True / False
Double counting is a proof technique: by showing that two different expressions count the same set of objects, you establish that the expressions must be equal.
TTrue
FFalse
Answer: True
True. This is exactly the power of double counting — it converts an algebraic identity into a combinatorial argument. Instead of proving C(n-1,k-1) + C(n-1,k) = C(n,k) by algebraic manipulation of factorials, you describe a single finite set and give two distinct counting procedures. Since both procedures count the same objects, they must produce the same number. The identity is proved by the argument's structure, not by calculation.
Question 4 True / False
In a valid double counting argument, both counting methods may count slightly different sets as long as the difference between the sets is predictable and can be corrected.
TTrue
FFalse
Answer: False
False. Both methods must count exactly the same set — not approximately the same, not the same up to a predictable correction. If the two methods count different sets, even sets that differ by a known amount, you cannot set the counts equal directly. You would need a separate argument to account for the difference, and at that point you are no longer doing double counting. The technique's entire validity rests on both methods producing counts of identical collections of objects.
Question 5 Short Answer
In the graph theory identity 'the sum of all vertex degrees equals twice the number of edges,' identify the set being counted and the two perspectives used.
Think about your answer, then reveal below.
Model answer: The set being counted is the collection of incidence pairs: ordered pairs (v, e) where vertex v is an endpoint of edge e. Perspective 1 (count by edges): each edge has exactly 2 endpoints, contributing 2 pairs, so the total is 2|E|. Perspective 2 (count by vertices): each vertex v contributes exactly deg(v) pairs — one for each edge incident to it — so the total is the sum of all vertex degrees. Setting these equal: sum of degrees = 2|E|.
This identity is a clean illustration of the double counting technique because the set (incidence pairs) is clearly defined and the two perspectives are natural. The proof requires no algebra — just the observation that both sides count the same pairs and the fact that a finite set has a unique size regardless of how it is counted.