Two-Set Formula

Combinatorics · Axiom Academy

Master the fundamental inclusion-exclusion principle for counting elements in two sets 1. The Double-Counting Problem Suppose we want to count how many elements are in the union of two sets A and B. Our first instinct might be to add |A| + |B|, but this creates a problem. Watch the animation: Elements that belong to both sets get counted twice! 2. The Inclusion-Exclusion Formula To fix the double-counting problem, we need to subtract the size of the intersection once. This gives us the fundamental two-set formula: This formula appears in many areas of mathematics and computer science. Let's see how it corrects the overcounting visually. We can prove this formula by analyzing how many times each element gets counted. Every element in A ∪ B falls into exactly one of three categories: Let's apply the formula to a concrete example: In a class of students, 15 study French, 12 study Spanish, and 5 study both languages. How many students study at least one language?

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