Inclusion-Exclusion Principle: Formula and Examples

The inclusion-exclusion principle counts elements in at least one of several overlapping sets. Adding set sizes double-counts the overlap, so you subtract the intersection back out: |A ∪ B| = |A| + |B| − |A ∩ B|.

Real counting problems almost always involve overlaps: students liking two subjects, numbers divisible by 2 or 3, survey respondents choosing multiple options. Inclusion-exclusion extends the fix to three or more sets with alternating signs.

Key Concepts

• Union |A ∪ B|: elements in A or B (or both).
• Intersection |A ∩ B|: elements in both, counted twice by |A| + |B|.
• Two-set formula: |A ∪ B| = |A| + |B| − |A ∩ B|.
• Three-set formula: |A ∪ B ∪ C| = (|A| + |B| + |C|) − (|A∩B| + |A∩C| + |B∩C|) + |A∩B∩C|.
• Pattern: add single sets, subtract pairwise intersections, add back triple intersections, subtract quadruple ones, alternating all the way.

Formulas

• Two sets: |A ∪ B| = |A| + |B| − |A ∩ B|: the subtraction corrects the double-counted overlap.
• Three sets: |A ∪ B ∪ C| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + |A ∩ B ∩ C|: the triple overlap was added thrice and subtracted thrice, so it is added back once.
• n sets: |∪Aᵢ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − … ± |∩Aᵢ|, alternating signs with intersection size.
• Complement form: elements in none of the sets = total − |union|, computed after inclusion-exclusion.

Worked Example

In a class of 100: 60 like mathematics, 50 physics, 40 chemistry; overlaps 30 (math+physics), 20 (math+chemistry), 25 (physics+chemistry), 10 all three. How many like at least one subject, and how many like none?

• Add singles: 60 + 50 + 40 = 150.
• Subtract pairs: 150 − 30 − 20 − 25 = 150 − 75 = 75.
• Add back triple: 75 + 10 = 85 students like at least one subject.
• None: 100 − 85 = 15 students like none of the three.

Check one group: students liking exactly math and physics number 30 − 10 = 20; in the formula they were added twice and subtracted once, netting one count. Every overlap level nets to one, which is why alternating signs work.

Common Misconceptions

• "Subtract the intersection once and you are done." That finishes only the two-set case. With three sets, subtracting pairwise intersections over-corrects the triple overlap, which must be added back. Each new set flips the correction again.
• "|A ∩ B| means elements in exactly both." It includes those also in C. The "exactly" groups are derived, not the raw intersections.
• "Inclusion-exclusion is only for three sets." The pattern continues to any number of sets, and it also counts derangements, onto functions and Euler's totient function.

Real-World Applications

• Survey analysis: counting respondents who chose at least one of several options without double-counting multi-choosers.
• Probability: P(A or B) = P(A) + P(B) − P(A and B) is inclusion-exclusion for probabilities.
• Number theory: counting integers up to n that are coprime to n (Euler's totient) uses inclusion-exclusion over prime divisors.

Inclusion-exclusion fixes double-counting with alternating corrections: add singles, subtract pairs, add back the triple intersection, and continue. Whenever you count a union of overlapping groups, this keeps the arithmetic honest.