Inclusion-Exclusion Principle

The inclusion-exclusion principle computes the probability (or size) of a union: $$P(A_1 \cup \cdots \cup A_n) = \sum_i P(A_i) - \sum_{i<j} P(A_i \cap A_j) + \sum_{i<j<k} P(A_i \cap A_j \cap A_k) - \cdots$$ Intuition: Adding all individual probabilities overcounts elements in intersections. Subtracting pairwise intersections undercounts elements in triple intersections. The alternating sum corrects exactly. When to use: Computing "at least one of" probabilities, counting derangements, computing probabilities of unions of non-disjoint events. This is a fundamental technique. Many "narrow" results (like the derangement formula) are derived via inclusion-exclusion.