Chapter 3: Principle of Inclusion and Exclusion
1. Introduction
In many counting problems, sets overlap. If we simply add sizes of sets, elements in the overlap get counted more than once.
The Principle of Inclusion and Exclusion (PIE) provides a systematic method to count the number of elements in the union of multiple sets by correcting overcounting.
2. Principle of Inclusion and Exclusion for Two Sets
Statement
For any two finite sets A and B:
[ |A ∪ B| = |A| + |B| - |A ∩ B| ]
Explanation
- |A| counts elements in A
- |B| counts elements in B
- |A ∩ B| is counted twice, so subtract it once
Example 1
In a class:
- 40 students study Mathematics
- 25 students study Physics
- 10 students study both
Find how many students study at least one subject.
[ |A ∪ B| = 40 + 25 - 10 = 55 ]
3. Principle of Inclusion and Exclusion for Three Sets
Statement
For three finite sets A, B, and C:
[ \begin{aligned} |A ∪ B ∪ C| =;& |A| + |B| + |C| \ &- |A ∩ B| - |A ∩ C| - |B ∩ C| \ &+ |A ∩ B ∩ C| \end{aligned} ]
Explanation
- Single sets are added
- Pairwise intersections are subtracted
- Triple intersection is added back
Example 2
In a survey:
- 60 people like Python
- 50 like Java
- 40 like C++
- 20 like Python & Java
- 15 like Python & C++
- 10 like Java & C++
- 5 like all three
Find how many like at least one language.
[ \begin{aligned} |A ∪ B ∪ C| =;& 60 + 50 + 40 \ &- (20 + 15 + 10) \ &+ 5 = 110 \end{aligned} ]
4. General Principle of Inclusion and Exclusion
For n finite sets ( A_1, A_2, \dots, A_n ):
[ \left|\bigcup_{i=1}^{n} A_i\right| ==================================
\sum |A_i|
\sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k|
\cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n| ]
Sign Pattern
- Add single sets
- Subtract pairwise intersections
- Add triple intersections
- Continue alternately
5. Counting the Complement
Often it is easier to count elements that do not satisfy a property.
[ |A| = |U| - |A'| ]
Example 3
How many integers between 1 and 100 are not divisible by 2, 3, or 5?
Let:
- A = multiples of 2
- B = multiples of 3
- C = multiples of 5
Total = 100
[ |A| = 50,; |B| = 33,; |C| = 20 ]
[ |A ∩ B| = 16,; |A ∩ C| = 10,; |B ∩ C| = 6 ]
[ |A ∩ B ∩ C| = 3 ]
[ |A ∪ B ∪ C| = 50 + 33 + 20 - (16 + 10 + 6) + 3 = 74 ]
[ \text{Required} = 100 - 74 = 26 ]
6. Inclusion–Exclusion in Derangements
A derangement is a permutation with no fixed points.
Number of derangements of n objects:
[ !n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!}\right) ]
Example 4
Number of ways to permute 4 objects so that no object is in its original position:
[ !4 = 4!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right) ]
[ = 24\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 9 ]
7. Applications in Computer Science
- Counting valid passwords
- Database query optimization
- Network reliability
- Error detection
- Counting strings with constraints
8. Common Exam Mistakes
- Forgetting the triple intersection
- Incorrect sign (+/–)
- Not defining sets clearly
- Overlooking complement method