Worked Examples: Counting and Structural Proofs

Conditional choices still multiply

Choose a chair and deputy from five distinct people. There are five choices for chair and four remaining choices for deputy for each chair, so 20 outcomes. The available deputy set depends on the chair, but its size is always four. Each ordered pair is produced once. No probability-independence assumption is needed. Transfer: if exactly one particular pair is forbidden, explain why a uniform 5·4 answer must be adjusted.

Inclusion-exclusion from one object's contribution

Suppose 12 people have one permission, nine have another, and five have both. Their union has 12+9−5=16 people. If the population is 20, four have neither; without that population the number having neither is undetermined. For three sets, an element in all three is counted three times and subtracted three times, so the triple intersection must be added back once.

A recurrence becomes a coefficient equation

For binary words avoiding 11, a₀=1,a₁=2 and aₙ=aₙ₋₁+aₙ₋₂ for n≥2. Writing A(x)=Σaₙxⁿ, summing only from n=2 gives A−1−2x=x(A−1)+x²A, hence A=(1+x)/(1−x−x²). The initial corrections are necessary. The same denominator with numerator one counts length-n tilings by lengths one and two, with different initial values. Transfer: reconstruct a₀..a₄ from this coefficient identity with the formula closed.

A matching witness plus an upper bound

Staff A and B can use station 1; staff C can use station 2 or 3. A–1,C–2 is a matching of size two. Since {A,B} has only one neighbor, at most one of them can be assigned, and C contributes at most one more. The upper bound two equals the witness size, proving optimality. This also proves a complete three-person assignment impossible, without enumerating every attempted assignment.

Why Euler's plane formula preserves components correctly

Start from a drawn forest with v vertices and c components: e=v−c and f=1, so v−e+f=1+c. Adding a noncrossing edge within one component splits a face: e and f each increase by one. Joining different components increases e by one, decreases c by one, and leaves f unchanged. Both operations preserve the formula. An arbitrary edge list supplies no chosen embedding or face count by itself.