Inclusion-Exclusion Examples

Combinatorics · Axiom Academy

EXAMPLE Inclusion-Exclusion Examples Master the Inclusion-Exclusion Principle through step-by-step problem solving Excellent work! You've mastered the Inclusion-Exclusion Principle. Here's what we learned: Two-Set Inclusion-Exclusion: For sets A and B, |A ∪ B| = |A| + |B| - |A ∩ B|. We add the sizes but subtract the overlap to avoid double-counting. Finding Intersections: When counting divisibility, A ∩ B consists of numbers divisible by lcm(a,b). For 2 and 3, this is 6. Floor Division Trick: To count multiples of k from 1 to n, use ⌊n/k⌋. This works because every k-th number is divisible by k. Why We Subtract: Simply adding |A| + |B| counts elements in A ∩ B twice, so we must subtract |A ∩ B| once to get the correct count. Extension to Three Sets: The principle extends: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|. We alternate signs: add individuals, subtract pairs, add triples. This principle is fundamental in combinatorics and appears in counting problems, probability, and even computer science algorithms. Practice with different divisibility problems and club membership scenarios to build intuition!

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