Inclusion-exclusion principle

The inclusion-exclusion principle extends the rule of sum by providing a way to count the number of elements in a union of sets which may share some elements in common.

The cardinality of the union of \(2\) finite sets \(A\) and \(B\), such that the sets may share some elements in common, is the sum of their individual cardinalities minus the cardinality of their intersection: $$|A \cup B| = |A| + |B| - |A \cap B|$$

To avoid overcounting, the number of elements that appear in both sets is subtracted. Let's see this principle in action!

How many ways are there for at least one of two differently-colored dice to come up as \(1\) after a roll? You could enumerate every single outcome to answer this question, but it's faster to use the inclusion-exclusion principle. Notice that there are \(6\) outcomes where one die shows up as \(1\), for each of the \(6\) numbers the other die can show. There are also \(6\) outcomes for the other die to show \(1.\) Be cautious though, because there is also \(1\) outcome where both dice show \(1.\) Subtract off this intersection to avoid counting snake-eyes twice: \(6 + 6 - 1 = 11.\)

In a room, there are \(5\) people who wear glasses, \(10\) people good at math, and \(3\) people good at math who wear glasses. How many people wear glasses or are good at math? (I am using the inclusive or here.) Let \(G\) be the set of people who wear glasses, and let \(M\) be the set of people good at math. \(|G| = 5\) and \(|M| = 10.\) Since there are \(3\) people good at math who also wear glasses, \(|G \cap M| = 3.\) By the inclusion-exclusion principle, the number of people who wear glasses or are good at math, \(|G \cup M|\), is equal to \(|G| + |M| - |G \cap M| = 5 + 10 - 3 = 12.\)

⚠ Recall that the logical analogue of the union operation is disjunction.
Contents

For three sets

With \(3\) sets, the formula becomes a bit more complicated, as the three-way intersection has to be added back in the end.

The cardinality of the union of \(3\) finite sets \(A\), \(B\), and \(C\), such that the sets may share some elements in common, is the sum of their individual cardinalities minus the cardinalities of all their \(2\)-way intersections plus the cardinality of their \(3\)-way intersection: $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$$
Image of the count being tweaked until every element is counted only once
The count is tweaked until every element is counted only once.

At a company, there are \(3\) web developers, each of whom have experience working on \(10\) projects. Every possible pair of them have each worked on \(3\) projects together. There is \(1\) project that all \(3\) of them worked on together. How many projects have been worked on in total? Let \(A\) be the set of projects worked on by the first web developer, let \(B\) be the set of projects worked on by the second web developer, and let \(C\) be the set of projects worked on by the third web developer. By the inclusion-exclusion principle for \(3\) sets, the total number of projects that have been worked on, \(|A \cup B \cup C|\), is \(|A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C| = 10 + 10 + 10 - 3 - 3 - 3 + 1 = 22.\)

For four or more sets

With even more sets, you can use the generalized form of the inclusion-exclusion principle, which has rules for adding and subtracting intersections based on the parity of the number of sets each intersection involves.

The cardinality of the union of finite sets \(A_1, ... A_n\), such that the sets may share some elements in common, is the sum of their individual cardinalities minus the cardinalities of all their even-way intersections plus the cardinalities of all their odd-way intersections: $$|A_1 \cup ... \cup A_n| = \sum\limits_{i=1}^{n}|A_i| - \underbrace{\sum\limits_{1 \leq i < j \leq n}^{}|A_i \cap A_j|}_{\text{all two-way intersections}} + \underbrace{\sum\limits_{1 \leq i < j < k \leq n}^{}|A_i \cap A_j \cap A_k|}_{\text{all three-way intersections}} + ... + (-1)^{n+1} \times \underbrace{|A_1 \cap ... \cap A_n|}_{n\text{-way intersection}}$$
⚠ Based on whether \(n\) is even or odd, you may need to subtract or add the cardinality of the \(n\)-way intersection at the end. That's what the \((-1)^{n+1}\) term is for.

Given four sets, \(A\), \(B\), \(C\), and \(D\), such that each set has \(10\) elements, all \(2\)-way intersections have \(4\) elements, all \(3\)-way intersections have \(3\) elements, and the \(4\)-way intersection has \(1\) element, how many elements are in \(A \cup B \cup C \cup D\)? By the inclusion-exclusion principle, there are \(4 \times 10 - \binom{4}{2} \times 4 + \binom{4}{3} \times 3 + (-1)^{4+1} \times 1 \times 1 = 27.\)

Logic & Proofs
Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form
Set Theory
Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof
Functions
Function • Floor function • Ceiling function • Inverse function
Algorithms
Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm
Relations
Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class
Number Theory
Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm
Induction
Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition
Combinatorics
Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle
Graph Theory
Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm
Recursion
Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort