General Inclusion-Exclusion

Combinatorics · Axiom Academy

LESSON General Inclusion-Exclusion Master the powerful formula for counting elements in unions of multiple sets For any finite collection of sets A₁, A₂, ..., Aₙ, the size of their union is given by: This formula has a beautiful structure: we alternate between adding and subtracting. First we add all individual set sizes, then subtract all pairwise intersections, then add back all triple intersections, and so on. 2. The Alternating Signs Pattern The formula alternates signs in a specific pattern: Size 2 intersections: Subtract (−) Size 4 intersections: Subtract (−) And so on, alternating with each size... Mathematically, the sign for a k-way intersection is (−1) k+1 . This ensures proper correction for overlaps. 3. Concrete Example: Three Sets Let's apply the formula to three sets A, B, and C. The general formula becomes: This expansion shows all the terms explicitly: Single sets (add): |A| + |B| + |C| Pairs (subtract): − |A ∩ B| − |A ∩ C| − |B ∩ C| The inclusion-exclusion principle works by carefully tracking how many times each element is counted: Consider an element x that appears in exactly k of the sets. We need to count it exactly once in the final union. The alternating sum ensures each element is counted exactly once: x is counted C(k,1) times when we add single sets x is subtracted C(k,2) times for pairs x is added C(k,3) times for triples This binomial identity guarantees that x contributes exactly 1 to the total count!

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