The Principle of Inclusion-Exclusion (PIE)
by aoum, Mar 26, 2025, 12:18 AM
The Principle of Inclusion-Exclusion (PIE): Counting Overlapping Sets
The Principle of Inclusion-Exclusion (PIE) is a powerful combinatorial technique used to calculate the size of the union of overlapping sets. It corrects for overcounting by systematically adding and subtracting the sizes of various intersections.
1. The Basic Form of Inclusion-Exclusion
For two finite sets
and 
, the size of their union is given by:
![\[
|A \cup B| = |A| + |B| - |A \cap B|.
\]](//latex.artofproblemsolving.com/6/f/3/6f3e15b9f2bdb4331acc41fa09951927b82d5014.png)
This formula accounts for the fact that elements in the intersection
are counted twice—once in 
and once in 
—so we subtract the overlap.
For three sets, , and 
:
![\[
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.
\]](//latex.artofproblemsolving.com/6/c/9/6c903bc32ca8e0072bc277d0f441b7ab7bfa3eca.png)
The pattern alternates between adding and subtracting the sizes of intersections of increasing complexity.
2. The General Formula of Inclusion-Exclusion
For
finite sets 
, the size of their union is:
![\[
\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < \dots < i_k \leq n} |A_{i_1} \cap \dots \cap A_{i_k}|.
\]](//latex.artofproblemsolving.com/d/f/b/dfbfeb1be8ae686a72f94d98c0a9545baf7c6094.png)
In words:
3. Proof of the Inclusion-Exclusion Formula
Consider any element
that belongs to at least one of the sets. We need to ensure each element is counted exactly once.
Define:
![\[
m(x) = \text{Number of sets } A_i \text{ that contain } x.
\]](//latex.artofproblemsolving.com/7/5/2/752600a41711228882174ede71b5c691681dfeb1.png)
In the PIE formula:
By summing over all elements, the formula holds by correcting these overcounts systematically.
4. Example: Counting Multiples
Find how many integers between
and 
are divisible by 
, 
, or 
.
Let:
Step 1: Count each set:
![\[
|A| = \left\lfloor \frac{100}{2} \right\rfloor = 50, \quad |B| = \left\lfloor \frac{100}{3} \right\rfloor = 33, \quad |C| = \left\lfloor \frac{100}{5} \right\rfloor = 20
\]](//latex.artofproblemsolving.com/e/d/c/edcadd78cbc24e4a2cf63e321f0b3882a570c65e.png)
Step 2: Subtract pairwise intersections:
![\[
|A \cap B| = \left\lfloor \frac{100}{6} \right\rfloor = 16, \quad |A \cap C| = \left\lfloor \frac{100}{10} \right\rfloor = 10, \quad |B \cap C| = \left\lfloor \frac{100}{15} \right\rfloor = 6
\]](//latex.artofproblemsolving.com/7/4/5/745c9fa1f79f7c5225b905fc989c0e1f758e7f93.png)
Step 3: Add the triple intersection:
![\[
|A \cap B \cap C| = \left\lfloor \frac{100}{30} \right\rfloor = 3
\]](//latex.artofproblemsolving.com/e/e/b/eebf2c896136ef1c5193cdf26481e2fc2fbb0816.png)
Step 4: Apply PIE:
![\[
|A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74
\]](//latex.artofproblemsolving.com/5/1/1/51166af1a180dadbb4afedc762bcd952ae33b57b.png)
Thus, there are
numbers between and divisible by , , or .
5. Applications of Inclusion-Exclusion
The principle of inclusion-exclusion has broad applications:
6. Advanced Generalization of Inclusion-Exclusion
For an arbitrary measure space
and measurable sets 
, the inclusion-exclusion formula generalizes to:
![\[
\mu \left( \bigcup_{i=1}^n A_i \right) = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < \dots < i_k \leq n} \mu(A_{i_1} \cap \dots \cap A_{i_k}).
\]](//latex.artofproblemsolving.com/8/6/9/8693c12d0a177189733a29628374e7a4c51b5b7c.png)
This allows the principle to be applied to continuous spaces and probability measures.
7. Derangements and Inclusion-Exclusion
A classical application of PIE is counting derangements—permutations where no object appears in its original position.
Let
represent the number of derangements of objects. Using PIE:
![\[
D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!},
\]](//latex.artofproblemsolving.com/b/2/f/b2f5e9eda7c3683161636aec79924d453e445c9e.png)
where the summation alternates signs based on how many fixed points to exclude.
8. Conclusion
The Principle of Inclusion-Exclusion is a fundamental tool in combinatorics, allowing precise counting of complex unions by carefully handling overlaps. It applies across multiple domains, including probability theory, graph theory, and set theory, providing a versatile method for solving intricate counting problems.
9. Principle of Inclusion-Exclusion Video by Sohil Rathi
References
The Principle of Inclusion-Exclusion (PIE) is a powerful combinatorial technique used to calculate the size of the union of overlapping sets. It corrects for overcounting by systematically adding and subtracting the sizes of various intersections.
Inclusion–exclusion illustrated by a Venn diagram for three sets
1. The Basic Form of Inclusion-Exclusion
For two finite sets
and 
, the size of their union is given by:![\[
|A \cup B| = |A| + |B| - |A \cap B|.
\]](http://latex.artofproblemsolving.com/6/f/3/6f3e15b9f2bdb4331acc41fa09951927b82d5014.png)
This formula accounts for the fact that elements in the intersection
are counted twice—once in 
and once in 
—so we subtract the overlap.For three sets
, , and 
:![\[
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.
\]](http://latex.artofproblemsolving.com/6/c/9/6c903bc32ca8e0072bc277d0f441b7ab7bfa3eca.png)
The pattern alternates between adding and subtracting the sizes of intersections of increasing complexity.
2. The General Formula of Inclusion-Exclusion
For
finite sets 
, the size of their union is:![\[
\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < \dots < i_k \leq n} |A_{i_1} \cap \dots \cap A_{i_k}|.
\]](http://latex.artofproblemsolving.com/d/f/b/dfbfeb1be8ae686a72f94d98c0a9545baf7c6094.png)
In words:
- Add the sizes of all individual sets.
- Subtract the sizes of all pairwise intersections.
- Add the sizes of all three-way intersections.
- Continue this pattern, alternating signs, until you reach the intersection of all sets.
3. Proof of the Inclusion-Exclusion Formula
Consider any element
that belongs to at least one of the sets. We need to ensure each element is counted exactly once.Define:
![\[
m(x) = \text{Number of sets } A_i \text{ that contain } x.
\]](http://latex.artofproblemsolving.com/7/5/2/752600a41711228882174ede71b5c691681dfeb1.png)
In the PIE formula:
- Each element is counted once for every set it belongs to.
- Each pairwise intersection removes elements counted twice.
- Each triple-wise intersection adds back elements removed too often.
- This alternation continues, ensuring each element is counted exactly once.
By summing over all elements, the formula holds by correcting these overcounts systematically.
4. Example: Counting Multiples
Find how many integers between
and 
are divisible by 
, 
, or 
.Let:
Step 1: Count each set:
![\[
|A| = \left\lfloor \frac{100}{2} \right\rfloor = 50, \quad |B| = \left\lfloor \frac{100}{3} \right\rfloor = 33, \quad |C| = \left\lfloor \frac{100}{5} \right\rfloor = 20
\]](http://latex.artofproblemsolving.com/e/d/c/edcadd78cbc24e4a2cf63e321f0b3882a570c65e.png)
Step 2: Subtract pairwise intersections:
![\[
|A \cap B| = \left\lfloor \frac{100}{6} \right\rfloor = 16, \quad |A \cap C| = \left\lfloor \frac{100}{10} \right\rfloor = 10, \quad |B \cap C| = \left\lfloor \frac{100}{15} \right\rfloor = 6
\]](http://latex.artofproblemsolving.com/7/4/5/745c9fa1f79f7c5225b905fc989c0e1f758e7f93.png)
Step 3: Add the triple intersection:
![\[
|A \cap B \cap C| = \left\lfloor \frac{100}{30} \right\rfloor = 3
\]](http://latex.artofproblemsolving.com/e/e/b/eebf2c896136ef1c5193cdf26481e2fc2fbb0816.png)
Step 4: Apply PIE:
![\[
|A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74
\]](http://latex.artofproblemsolving.com/5/1/1/51166af1a180dadbb4afedc762bcd952ae33b57b.png)
Thus, there are
numbers between and divisible by , , or .5. Applications of Inclusion-Exclusion
The principle of inclusion-exclusion has broad applications:
- Counting Problems: Solving problems involving overlapping categories.
- Probability Theory: Finding the probability of the union of events.
- Combinatorics: Counting permutations with restrictions.
- Set Theory: Analyzing intersections and unions of large collections.
- Graph Theory: Counting subgraphs and other combinatorial objects.
6. Advanced Generalization of Inclusion-Exclusion
For an arbitrary measure space
and measurable sets 
, the inclusion-exclusion formula generalizes to:![\[
\mu \left( \bigcup_{i=1}^n A_i \right) = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < \dots < i_k \leq n} \mu(A_{i_1} \cap \dots \cap A_{i_k}).
\]](http://latex.artofproblemsolving.com/8/6/9/8693c12d0a177189733a29628374e7a4c51b5b7c.png)
This allows the principle to be applied to continuous spaces and probability measures.
7. Derangements and Inclusion-Exclusion
A classical application of PIE is counting derangements—permutations where no object appears in its original position.
Let
represent the number of derangements of objects. Using PIE:![\[
D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!},
\]](http://latex.artofproblemsolving.com/b/2/f/b2f5e9eda7c3683161636aec79924d453e445c9e.png)
where the summation alternates signs based on how many fixed points to exclude.
8. Conclusion
The Principle of Inclusion-Exclusion is a fundamental tool in combinatorics, allowing precise counting of complex unions by carefully handling overlaps. It applies across multiple domains, including probability theory, graph theory, and set theory, providing a versatile method for solving intricate counting problems.
9. Principle of Inclusion-Exclusion Video by Sohil Rathi
References
- R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Edition (Addison-Wesley, 1994).
- I. Anderson, A First Course in Discrete Mathematics (Springer, 2001).
- Wikipedia: Inclusion-Exclusion Principle.
- AoPS: Principle of Inclusion-Exclusion.
March 2025