Questions: Inclusion-Exclusion Principle

Question 1

An element belongs to exactly 3 of the n sets in an inclusion-exclusion computation. How many times does this element contribute to the final count of |A₁ ∪ A₂ ∪ ... ∪ Aₙ|?

• A. 3 times — once for each set it belongs to
• B. 1 time — the alternating sum reduces to exactly 1 for any element belonging to k ≥ 1 sets
• C. 0 times — it cancels out because C(3,1) − C(3,2) + C(3,3) = 3 − 3 + 1 = 1, which is not 0
• D. 7 times before corrections are applied

Answer: (B)

Every element in the union is counted exactly once. An element in exactly k sets contributes C(k,1) − C(k,2) + C(k,3) − ... to the alternating sum. By the binomial theorem applied to (1−1)^k, this alternating sum equals 1 for any k ≥ 1. For k = 3: C(3,1) − C(3,2) + C(3,3) = 3 − 3 + 1 = 1. This is the entire point of the alternating sign structure — it is precisely calibrated to count each element once regardless of how many sets it belongs to.

Question 2

You want to count integers in [1, 100] not divisible by 2, 3, or 5. You observe that every pair of these primes produces the same intersection-size behavior, and every triple does too. What does this symmetry allow?

• A. Nothing — you must still enumerate all 2³ − 1 = 7 intersection terms individually
• B. Collapsing the formula to a weighted sum: one representative intersection per order, multiplied by C(n,k)
• C. Skipping the pairwise correction terms entirely since the primes are distinct
• D. Applying inclusion-exclusion only to pairwise intersections and ignoring higher-order ones

Answer: (B)

When all k-fold intersections have the same size (regardless of which k sets you pick), the formula collapses from summing all 2ⁿ − 1 terms individually to a sum of n + 1 terms: Σ(−1)^k · C(n,k) · |typical k-fold intersection|. For counting integers not divisible by any prime in a list, |Aᵢ₁ ∩ ... ∩ Aᵢₖ| depends only on k (it's ⌊100/(p₁·p₂···pₖ)⌋). Recognizing and exploiting this symmetry is what makes the computation tractable.

Question 3

As n grows large, approximately 37% of all permutations of n elements are derangements — permutations where no element is in its original position.

• T. True
• F. False

Answer: True

The derangement formula D(n) = n!(1 − 1/1! + 1/2! − 1/3! + ... ± 1/n!) comes directly from inclusion-exclusion. As n → ∞, the sum 1 − 1/1! + 1/2! − ... converges to e⁻¹ ≈ 0.368. So D(n)/n! → 1/e, meaning roughly 36.8% of all permutations are derangements, a proportion that stabilizes quickly even for small n.

Question 4

In the inclusion-exclusion formula, terms involving an even number of sets are added (positive sign), while terms involving an odd number of sets are subtracted (negative sign).

• T. True
• F. False

Answer: False

This is backwards. Single-set terms (odd, k=1) are added; pairwise terms (even, k=2) are subtracted; triple terms (odd, k=3) are added; and so on. Positive signs go with odd-cardinality intersections; negative signs go with even-cardinality intersections. The rule is: (−1)^(k+1) for k-fold intersections — positive when k is odd, negative when k is even.

Question 5

Why does the alternating sum in inclusion-exclusion guarantee that every element in the union is counted exactly once? Use the binomial theorem in your answer.

Model answer: An element appearing in exactly k of the n sets is counted C(k,1) times in the single-set terms, subtracted C(k,2) times in the pairwise terms, added C(k,3) times in the triple terms, and so on. Its total contribution is C(k,1) − C(k,2) + C(k,3) − ... + (−1)^(k+1)C(k,k). By the binomial theorem, (1−1)^k = Σ(−1)^j C(k,j) = 0, so Σ(−1)^(j+1) C(k,j) = 1. The alternating sum equals exactly 1 for every k ≥ 1, which means every element is counted once regardless of how many sets it belongs to.

This is the mathematical heart of inclusion-exclusion. The alternating sign structure is not a clever trick — it is the unique correction that maintains a count of 1 per element. The binomial identity (1−1)^k = 0 is what makes it work, and recognizing this connection reveals why the formula must have alternating signs and why there is no simpler alternative.