Inclusion-Exclusion Principle — Definition, Formula & Examples

The Inclusion-Exclusion Principle is a counting technique that finds the size of the union of multiple sets by adding individual set sizes, then correcting for overcounting by subtracting pairwise intersections, adding back triple intersections, and so on.

For finite sets $A_1, A_2, \ldots, A_n$ , the cardinality of their union is given by $|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap A_2 \cap \cdots \cap A_n|$ . The sum alternates in sign across all nonempty subsets of the index set.

Key Formula

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

Where:

$|A|, |B|, |C|$ = Sizes of the individual sets
$|A \cap B|$ = Number of elements in both A and B
$|A \cup B \cup C|$ = Number of elements in at least one of the three sets

How It Works

When you simply add the sizes of two or more sets, elements that belong to more than one set get counted multiple times. The principle systematically corrects this: first subtract every pairwise overlap, then add back every triple overlap (since those were subtracted too many times), and continue alternating. For two sets, you only need one correction term. For three sets, you need three pairwise subtractions and one triple addition. The pattern generalizes to any number of sets.

Worked Example

Problem: In a class of 100 students, 40 study French, 35 study Spanish, and 20 study German. Also, 12 study both French and Spanish, 8 study both French and German, 6 study both Spanish and German, and 2 study all three languages. How many students study at least one of the three languages?

Add individual sets: Sum the sizes of each set.

40 + 35 + 20 = 95

Subtract pairwise intersections: Remove the double-counted elements.

95 - 12 - 8 - 6 = 69

Add back triple intersection: The 2 students in all three sets were subtracted too many times, so add them back.

69 + 2 = 71

Answer: 71 students study at least one of the three languages.

Why It Matters

This principle is essential in combinatorics courses whenever direct counting is difficult but counting overlaps is manageable. It underpins derangement formulas, Euler's totient function in number theory, and probability calculations for unions of non-mutually-exclusive events.

Common Mistakes

Mistake: Forgetting to alternate signs and simply subtracting all intersection terms.

Correction: After subtracting pairwise intersections, you must add back triple intersections, subtract quadruple intersections, and so on. Each level of intersection alternates sign: subtract, add, subtract, add.