Inclusion-Exclusion Summary

Combinatorics · Axiom Academy

SUMMARY Inclusion-Exclusion Principle Let's review the key counting techniques for handling overlapping sets and complex restrictions. Foundation: Corrects overcounting when sets overlap by alternately adding and subtracting intersection sizes Two Sets: |A ∪ B| = |A| + |B| - |A ∩ B| Three Sets: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C| Pattern: Add singles, subtract pairs, add triples, subtract quadruples, and so on n Sets: For sets A₁, A₂, ..., Aₙ, the union size alternates signs across intersection sizes Structure: Sum over all non-empty subsets S ⊆ 1,2,...,n , with sign (-1)^(|S|+1) Key Insight: Each element is counted exactly once when all overlaps are accounted for Complementary Counting: Often easier to count what's excluded and subtract from the total Definition: A permutation where no element appears in its original position Notation: D(n) or !n denotes the number of derangements of n objects Formula: D(n) = n! · (1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!) Approximation: For large n, D(n) ≈ n!/e where e ≈ 2.71828 Probability: Probability of a random derangement approaches 1/e ≈ 36.8% as n increases Definition: φ(n) counts integers from 1 to n that are coprime to n (gcd = 1) Prime Power: φ(p^k) = p^k - p^(k-1) = p^k(1 - 1/p) Multiplicative: If gcd(m,n) = 1, then φ(mn) = φ(m)·φ(n) General Formula: φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₖ) for prime factors p₁, p₂, ..., pₖ

This is the written version of the interactive lesson above. See the full Combinatorics course.