Inclusion-exclusion principle: Question bank — Maths deep dive

True or false — justify

Recall Verdict

and reason If $A \cap B = \emptyset$ then the two-set formula is wrong and should not be used ::: False — it is still correct: $∣ A \cap B ∣ = 0$ , so $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - 0 = ∣ A ∣ + ∣ B ∣$ , which is exactly the disjoint-addition rule. See Probability Axioms additivity as this special case. In the general formula, the sign of a term depends on how many sets that intersection joins ::: True — a $k$ -fold intersection carries sign $(- 1)^{k + 1}$ : odd $k$ gets $+$ , even $k$ gets $-$ , regardless of which sets are involved. Adding $∣ A ∣ + ∣ B ∣ + ∣ C ∣$ counts an element lying in all three sets exactly three times ::: True — it is caught once inside each of $∣ A ∣$ , $∣ B ∣$ , $∣ C ∣$ , so three additions; the later $-$ pairs and $+$ triple corrections then net it back to one. The union $A \cup B \cup C$ counts a student who likes exactly one drink and a student who likes all three the same way ::: True — the union means "in one or more sets," so both are counted exactly once; "exactly one" is a different quantity with different coefficients. Inclusion–exclusion can give a negative answer if you have enough sets ::: False — the final count is a cardinality (or probability), always $\geq 0$ ; individual terms alternate sign but the total is provably the true size of the union. Stopping after "subtract all the pairwise intersections" gives a lower bound on the true union size ::: True — this is a Bonferroni bound: truncating I–E after a subtraction under-counts, after an addition over-counts, so partial sums bracket the answer. The identity $\sum_{k = 0}^{m} (- 1)^{k} (k m) = 0$ is the reason every element is counted once ::: True — it is $(1 - 1)^{m} = 0$ from the Binomial Theorem; splitting off the $k = 0$ term forces the remaining alternating sum to equal $1$ . For the derangement application, $∣ A_{i} ∣ = (n - 1)!$ because fixing one position leaves the rest free ::: True — $A_{i}$ = permutations fixing position $i$ ; the other $n - 1$ symbols permute freely, giving $(n - 1)!$ arrangements. See Derangements & Permutations.

Spot the error

Recall Find the flaw in each "solution"

"Since I already subtracted $∣ A \cap B ∣$ , $∣ A \cap C ∣$ , and $∣ B \cap C ∣$ , the three-set union is $\sum ∣ A_{i} ∣$ minus those three." ::: Wrong — an all-three element is now at $3 - 3 = 0$ , so it is missing entirely; you must add back $+ ∣ A \cap B \cap C ∣$ once. "The survey says $60 + 50 + 40 = 150$ students out of 100 like a drink, so the data is impossible." ::: Wrong reading — $150$ is the sum with double/triple counting; I–E removes the overlaps down to $95 \leq 100$ , which is consistent. "To count multiples of 3 or 5 below 30, I subtract multiples of $3 \times 5 = 15$ ." ::: Correct here only because $g cd (3, 5) = 1$ ; the overlap is multiples of $lcm (3, 5)$ , and $lcm = 15$ equals the product only for coprime numbers. "I'm told $∣ A \cup B ∣ = 40$ , $∣ A ∣ = 30$ , $∣ B ∣ = 20$ , so $∣ A \cup B ∣ = 30 + 20 - ∣ A \cap B ∣ = 50 - ∣ A \cap B ∣$ and I re-apply the formula to get the union." ::: Circular — the union is given; use the formula backwards to find $∣ A \cap B ∣ = 30 + 20 - 40 = 10$ , don't re-derive what you already know. "For 'exactly one of $A, B, C$ ' I just take $∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣$ ." ::: Wrong — that is the union (at least one). "Exactly one" uses different coefficients: $\sum ∣ A_{i} ∣ - 2 \sum ∣ A_{i} \cap A_{j} ∣ + 3∣ A \cap B \cap C ∣$ . "In the alternating-sign proof, the $k = 0$ term is irrelevant because our sum starts at $k = 1$ ." ::: Wrong — the $k = 0$ term $(0 m) = 1$ is precisely what we peel off from $(1 - 1)^{m} = 0$ to prove the $k \geq 1$ sum equals $1$ ; it is the anchor of the argument.

Why questions

Recall Explain the mechanism

Why do the signs alternate rather than, say, all being minus after the first? ::: Because an element in $m$ sets appears $(k m)$ times at level $k$ , and only the alternating pattern $(- 1)^{k + 1}$ makes $\sum_{k = 1}^{m} (- 1)^{k + 1} (k m) = 1$ hold for every $m$ at once. Why is the two-set case the "atom" from which everything is built? ::: Every over-count is fundamentally a pairwise double-count; higher terms are just the recursive fix-ups for elements shared by more than two sets, each correcting the previous layer. Why does dividing every term by $∣ S ∣$ turn the counting formula into the probability formula? ::: Cardinalities become relative frequencies $∣ A ∣/∣ S ∣ = P (A)$ under equally-likely outcomes; the additive structure is preserved, so I–E holds identically for probabilities. Why does the derangement count use I–E on "at least one fixed point" rather than counting no-fixed-point directly? ::: "No fixed point" is a hard negative condition; I–E naturally counts unions of the "fixes position $i$ " events, and $D_{n} = n! - (at least one fixed point)$ converts easily. Why can't we count the union by just listing intersections without the $(k n)$ combinatorics in the proof? ::: An element in $m$ sets belongs to $(k m)$ different $k$ -fold intersections, so the combinatorial count of how many terms hit it is exactly what the proof must track. Why does I–E reduce to plain additivity when all sets are pairwise disjoint? ::: All intersections are empty, so every correction term is $0$ and only $\sum ∣ A_{i} ∣$ survives — recovering the disjoint sum. See Set Theory & Venn Diagrams.

Edge cases

Recall Boundaries and degenerate inputs

What does I–E give when $n = 1$ (a single set)? ::: Just $∣ A_{1} ∣$ — the sum has one term, sign $(- 1)^{1 + 1} = + 1$ , and no intersections exist; the formula degenerates gracefully. What if one of the sets is empty, $A_{j} = \emptyset$ ? ::: Every term containing $A_{j}$ has size $0$ , so it silently drops out; the answer equals the union of the remaining sets — no special handling needed. What if two sets are identical, $A = B$ ? ::: Then $∣ A \cap B ∣ = ∣ A ∣ = ∣ B ∣$ , so $∣ A \cup B ∣ = ∣ A ∣ + ∣ A ∣ - ∣ A ∣ = ∣ A ∣$ , correctly reporting one set's worth — the formula self-corrects the redundancy. What happens to the alternating-sum proof for an element in $m = 0$ sets (outside the union)? ::: The proof only claims correctness for $m \geq 1$ ; an element in no set contributes $0$ terms and is counted $0$ times, which is exactly right since it is not in the union. Does I–E work if the universe is infinite but each $A_{i}$ is finite? ::: Yes — the formula only uses the finite cardinalities $∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣$ ; the surrounding universe's size never appears in the counting version. If all $n$ sets are mutually equal, how many distinct nonzero intersection values appear? ::: Only one — every $k$ -fold intersection equals the common set, so the total telescopes via $\sum_{k = 1}^{n} (- 1)^{k + 1} (k n) = 1$ back to a single set's size.

Connections

Parent: Inclusion–exclusion principle
Set Theory & Venn Diagrams — disjoint pieces and overlaps behind every trap here
Bonferroni Inequalities — the truncation bounds tested above
Binomial Theorem — source of the $(1 - 1)^{m} = 0$ identity
Counting Principles & Combinatorics — why $(k m)$ terms hit each element
Probability Axioms — disjoint additivity as the degenerate case
Derangements & Permutations — the fixed-point application