You want to count permutations of {1, 2, 3, 4} where no element maps to itself. You define Aᵢ as the set of permutations that fix element i. Which approach correctly applies the inclusion-exclusion framework?
ASubtract from 4! the number of permutations that fix exactly one element
BApply inclusion-exclusion: compute |total| − |A₁∪A₂∪A₃∪A₄| using alternating sums over all intersection sizes
CDivide 4! by the number of fixed-point arrangements
DList all 24 permutations and remove those with any fixed points by inspection
This is the derangement problem, the canonical application of inclusion-exclusion to 'bad properties.' The correct setup is to let Aᵢ be the set of permutations fixing element i, then count the complement of their union using the IE formula: subtract sizes of individual sets, add back pairwise intersections, subtract triple intersections, etc. The alternating sum is the heart of the technique — option A would only remove permutations with exactly one fixed point, missing those with two or more.
Question 2 Multiple Choice
The Möbius inversion formula on the Boolean lattice of subsets gives μ(S,T) = (−1)^|T\S|. How does this relate to the standard inclusion-exclusion principle?
AIt is a special case applicable only to derangements, not to surjections or chromatic polynomials
BIt reveals that the alternating signs in inclusion-exclusion arise from a universal algebraic inversion theorem on posets, not from properties specific to each problem
CIt replaces inclusion-exclusion for advanced problems but is algebraically unrelated to the basic formula
DIt proves that inclusion-exclusion always requires exactly n alternating terms regardless of the problem structure
The Möbius function on the Boolean lattice of subsets is exactly (−1)^|T\S|, which is the alternating sign appearing in inclusion-exclusion. This reveals that IE is not a clever counting trick specific to unions — it is a special case of a general inversion theorem that works on any partially ordered set. Recognizing this unifies derangements, surjections, chromatic polynomials, and permanent calculations as instances of the same algebraic structure.
Question 3 True / False
The probability that a uniformly random permutation of n elements is a derangement approaches 1/e as n grows, a fact that follows directly from the inclusion-exclusion formula.
TTrue
FFalse
Answer: True
The derangement count D(n) = n!(1 − 1/1! + 1/2! − ⋯ + (−1)ⁿ/n!) comes directly from inclusion-exclusion. Dividing by n! gives the probability: 1 − 1 + 1/2! − 1/3! + ⋯, which is the truncated Taylor series for e⁻¹. As n → ∞, this converges to exactly 1/e ≈ 0.368. This is a striking connection between combinatorics and analysis that emerges purely from the alternating sum structure.
Question 4 True / False
Inclusion-exclusion can mainly count elements in unions of sets; it can seldom be applied to problems about functions, graph colorings, or restricted permutations.
TTrue
FFalse
Answer: False
Inclusion-exclusion is a general technique for counting objects that avoid a collection of 'bad' properties. For surjections, the 'bad property' is missing an output element. For chromatic polynomials, it is using the same color on adjacent vertices. For derangements, it is fixing an element. In each case, the strategy is the same: define Aᵢ for each bad condition, compute intersection sizes, and assemble the alternating sum. The union-of-sets formulation is the simplest instance of this general structure.
Question 5 Short Answer
Describe the general problem-solving mindset that inclusion-exclusion enables. What makes a problem recognizable as an IE problem, and what role does the alternating-sign structure play?
Think about your answer, then reveal below.
Model answer: A problem is suited to inclusion-exclusion when you need to count objects satisfying 'none of a collection of bad conditions' and when directly counting the valid objects is hard but counting objects satisfying each bad condition (and their intersections) is easy. The alternating sum — add singletons, subtract pairs, add triples — systematically corrects for overcounting: objects violating k conditions were excluded k times, added back C(k,2) times, and so on; the alternating sum reduces the net count to exactly 1 exclusion per violating object. Recognizing this structure transforms IE from a formula into a problem-solving mindset applicable across permutations, functions, and graph theory.
The key is identifying what the 'bad properties' are and whether intersection sizes can be computed. Once you see IE as 'counting things that avoid all bad properties,' the problem of derangements (no fixed points), surjections (no missed output), and chromatic polynomials (no monochromatic edges) all become instances of the same reasoning pattern.