How do you handle elements not in any set?

To find elements outside all sets, subtract the PIE union result from the size of the universal set: $|U| - |A_1 \cup \dots \cup A_n|$.

What if the sets are mutually exclusive?

If the sets are disjoint, all intersection sizes are zero. The formula reduces to the simple sum of the individual set sizes.

Does this work for infinite sets?

No. The principle of inclusion-exclusion requires finite sets or spaces with finite measure to avoid undefined operations like $\infty - \infty$.

How to count with the inclusion-exclusion principle

The principle of inclusion-exclusion (PIE) computes the size of the union of multiple sets by adding the sizes of the individual sets and recursively adjusting for the sizes of their intersections.

It applies whenever you need to count elements that belong to at least one of several overlapping finite sets, correcting for elements that are counted multiple times.

The setup

Define a finite collection of sets $A_1, A_2, \dots, A_n$ . The objective is to calculate the cardinality of their union, denoted as $|A_1 \cup A_2 \cup \dots \cup A_n|$ .

The steps

Sum the cardinalities of the individual sets: $\sum_{i=1}^n |A_i|$ .
Subtract the sizes of all pairwise intersections: $-\sum_{1 \le i < j \le n} |A_i \cap A_j|$ .
Add the sizes of all three-way intersections: $+\sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k|$ .
Continue alternating signs for each level of intersection up to the $n$ -way intersection: $(-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$ .
Sum these terms to obtain the total cardinality.

Checking the result

Verify that the resulting cardinality is a non-negative integer. Ensure the result does not exceed the cardinality of the universal set $|U|$ from which the elements are drawn. For $n \le 3$ , verify individual regions using a Venn diagram.

Common errors

Failing to alternate signs at each depth of intersection. Miscalculating the sizes of the intersections, particularly by incorrectly assuming independence (e.g., multiplying sizes rather than finding the actual intersection set).

Worked example

Find the number of integers from 1 to 100 inclusive that are divisible by 2, 3, or 5.

Let $U = \{1, 2, \dots, 100\}$ . Let $A$ be the set of integers divisible by 2. Let $B$ be the set of integers divisible by 3. Let $C$ be the set of integers divisible by 5.

Single sets: $|A| = \lfloor 100/2 \rfloor = 50$ $|B| = \lfloor 100/3 \rfloor = 33$ $|C| = \lfloor 100/5 \rfloor = 20$

Three-way intersection: $|A \cap B \cap C| = \lfloor 100/30 \rfloor = 3$

Apply the inclusion-exclusion principle: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ $|A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3$ $|A \cup B \cup C| = 103 - 32 + 3$ $|A \cup B \cup C| = 74$

There are 74 such integers.

FAQ

Run your own problem

Answer form

References: Discrete Mathematics and Its Applications by Kenneth H. Rosen · Concrete Mathematics by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik