26-06 — Inclusion-Exclusion Principle

Phase: Combinatorics | Subject: 26-06 Prerequisites: 26-01-counting-principles.md, 26-03-combinations.md Next subject: 26-07-recurrence-relations.md

Learning Objectives

By the end of this subject, you will be able to:

1. State the Inclusion-Exclusion Principle for 2 and 3 sets
2. Write the general formula for $n$ sets
3. Apply Inclusion-Exclusion to counting with overlapping conditions
4. Derive and apply the derangement formula
5. Use Inclusion-Exclusion in number theory (counting integers with prime properties)

Core Content

The Principle for Two Sets

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

Why: $|A| + |B|$ double-counts the intersection, so subtract it once.

Three Sets

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

Pattern: Add singles, subtract pairs, add triples — alternating.

General Formula (n sets)

$$\left|\bigcup_{i=1}^{n} A_i\right| = \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 \cdots \cap A_n|$$

$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < \cdots < i_k \leq n} |A_{i_1} \cap \cdots \cap A_{i_k}|$$

Complementary Form

Often it's easier to count what we DON'T want:

$$|A_1^c \cap A_2^c \cap \cdots \cap A_n^c| = |U| - \left|\bigcup_{i=1}^{n} A_i\right|$$

where $U$ is the universal set.

Derangements

A derangement is a permutation with no fixed points: $\sigma(i) \neq i$ for all $i$.

Let $D_n$ = number of derangements of $n$ elements.

$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$$

Derivation: Let $A_i$ = permutations where $i$ is fixed. $|A_i| = (n-1)!$, $|A_i \cap A_j| = (n-2)!$, etc.

$D_n = n! - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \cdots = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots$

$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$.

Note: $D_n \approx n!/e$ for large $n$ (since $\sum_{k=0}^{\infty} (-1)^k/k! = 1/e$).

Key Terms

• Inclusion-Exclusion Principle
• Derangement
• Fixed Point

Worked Examples

Example 1: Divisibility Count

How many integers from 1 to 1000 are divisible by 2, 3, or 5?

Solution: Let $A$ = multiples of 2: $|A| = \lfloor 1000/2 \rfloor = 500$. $B$ = multiples of 3: $|B| = \lfloor 1000/3 \rfloor = 333$. $C$ = multiples of 5: $|C| = \lfloor 1000/5 \rfloor = 200$.

Intersections: $|A \cap B| = \lfloor 1000/6 \rfloor = 166$. $|A \cap C| = \lfloor 1000/10 \rfloor = 100$. $|B \cap C| = \lfloor 1000/15 \rfloor = 66$. $|A \cap B \cap C| = \lfloor 1000/30 \rfloor = 33$.

Inclusion-Exclusion: $|A \cup B \cup C| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$.

Example 2: Derangements of 4 Items

How many derangements of {1, 2, 3, 4}?

Solution: $D_4 = 4!(1 - 1 + 1/2 - 1/6 + 1/24) = 24(0 - 0 + 0.5 - 0.1667 + 0.0417) = 24 \times 0.375 = 9$.

The derangements are: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.

Example 3: Three Conditions

In a class of 100 students, 60 study math, 50 study physics, 40 study chemistry. 30 study math and physics, 25 study math and chemistry, 20 study physics and chemistry, and 10 study all three. How many study at least one? How many study none?

Solution: $|M \cup P \cup C| = 60 + 50 + 40 - 30 - 25 - 20 + 10 = 85$ study at least one. $100 - 85 = 15$ study none.

Quiz

Q1: What does the concept of Inclusion-Exclusion Principle primarily refer to in this subject?

A) A computational error related to Inclusion-Exclusion Principle B) The definition and application of Inclusion-Exclusion Principle C) A visual representation of Inclusion-Exclusion Principle D) A historical anecdote about Inclusion-Exclusion Principle

Correct: B)

• If you chose A: This is incorrect. Inclusion-Exclusion Principle is defined as: the definition and application of inclusion-exclusion principle. The other options describe different aspects that are not the primary focus.
• If you chose B: Inclusion-Exclusion Principle is defined as: the definition and application of inclusion-exclusion principle. The other options describe different aspects that are not the primary focus. Correct!
• If you chose C: This is incorrect. Inclusion-Exclusion Principle is defined as: the definition and application of inclusion-exclusion principle. The other options describe different aspects that are not the primary focus.
• If you chose D: This is incorrect. Inclusion-Exclusion Principle is defined as: the definition and application of inclusion-exclusion principle. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) An unrelated formula from a different topic B) The inverse operation of the formula in question C) |A \cup B| = |A| + |B| - |A \cap B| D) A simplified version of |A \cup B| = |A| + |B| - |A ...

Correct: C)

• If you chose A: This is incorrect. The formula |A \cup B| = |A| + |B| - |A \cap B| is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: This is incorrect. The formula |A \cup B| = |A| + |B| - |A \cap B| is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: The formula |A \cup B| = |A| + |B| - |A \cap B| is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose D: This is incorrect. The formula |A \cup B| = |A| + |B| - |A \cap B| is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Derangement?

A) It replaces all other methods in this domain B) It is used to derangement in mathematical analysis C) It is primarily a historical notation system D) It is used only in advanced research contexts

Correct: B)

• If you chose A: This is incorrect. Derangement serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: Derangement serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose C: This is incorrect. Derangement serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Derangement serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Fixed Point is TRUE?

A) Fixed Point is mentioned only as a historical footnote B) Fixed Point is an advanced topic beyond this subject's scope C) Fixed Point is a fundamental concept covered in this subject D) Fixed Point is not related to this subject

Correct: C)

• If you chose A: This is incorrect. Fixed Point is a fundamental concept covered in this subject. This subject covers Fixed Point as part of its core content.
• If you chose B: This is incorrect. Fixed Point is a fundamental concept covered in this subject. This subject covers Fixed Point as part of its core content.
• If you chose C: Fixed Point is a fundamental concept covered in this subject. This subject covers Fixed Point as part of its core content. Correct!
• If you chose D: This is incorrect. Fixed Point is a fundamental concept covered in this subject. This subject covers Fixed Point as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) Derangements of 4 Items B) An unrelated numerical value C) A different result from a common mistake D) The inverse of the correct answer

Correct: A)

• If you chose A: The worked examples show that the result is Derangements of 4 Items. The other options represent common errors. Correct!
• If you chose B: This is incorrect. The worked examples show that the result is Derangements of 4 Items. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is Derangements of 4 Items. The other options represent common errors.
• If you chose D: This is incorrect. The worked examples show that the result is Derangements of 4 Items. The other options represent common errors.

Q6: How are Fixed Point and The Principle For Two Sets related?

A) Fixed Point is a special case of The Principle For Two Sets B) Fixed Point and The Principle For Two Sets are closely related concepts C) Fixed Point and The Principle For Two Sets are completely unrelated topics D) Fixed Point is the inverse of The Principle For Two Sets

Correct: B)

• If you chose A: This is incorrect. Both Fixed Point and The Principle For Two Sets are covered in this subject as interconnected topics.
• If you chose B: Both Fixed Point and The Principle For Two Sets are covered in this subject as interconnected topics. Correct!
• If you chose C: This is incorrect. Both Fixed Point and The Principle For Two Sets are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Fixed Point and The Principle For Two Sets are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Three Sets?

A) Three Sets is always computed the same way in all contexts B) The main error with Three Sets is using it when it is not needed C) A common mistake is confusing Three Sets with a similar concept D) Three Sets has no common misconceptions

Correct: C)

• If you chose A: This is incorrect. Students often confuse Three Sets with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Three Sets with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: Students often confuse Three Sets with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose D: This is incorrect. Students often confuse Three Sets with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply General Formula (N Sets)?

A) Apply General Formula (N Sets) to solve problems in this subject's domain B) Avoid General Formula (N Sets) unless explicitly instructed C) General Formula (N Sets) is not practically useful D) Use General Formula (N Sets) only in pure mathematics contexts

Correct: A)

• If you chose A: General Formula (N Sets) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose B: This is incorrect. General Formula (N Sets) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: This is incorrect. General Formula (N Sets) is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: This is incorrect. General Formula (N Sets) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. Among integers 1-100, how many are divisible by 3 or 7?
   

   Click for answer

   $|A \cup B| = \lfloor 100/3 \rfloor + \lfloor 100/7 \rfloor - \lfloor 100/21 \rfloor = 33 + 14 - 4 = 43$.

2. How many 3-letter strings from {A,B,C,D,E} contain at least one vowel?
   

   Click for answer

   Total $= 5^3 = 125$. Without vowels (consonants only) $= 3^3 = 27$. With at least one vowel $= 125 - 27 = 98$.

3. Compute $D_5$ (number of derangements of 5 items).
   

   Click for answer

   $D_5 = 5!(1 - 1 + 1/2 - 1/6 + 1/24 - 1/120) = 120(0.5 - 0.1667 + 0.0417 - 0.00833) = 120 \times 0.36667 = 44$.

4. Among permutations of {1,2,3,4,5}, how many have at least one fixed point?
   

   Click for answer

   Total $= 5! = 120$. Derangements $= 44$. So $120 - 44 = 76$ have at least one fixed point.

5. 200 students: 100 take French, 80 take Spanish, 60 take German. 40 take French+Spanish, 30 take French+German, 20 take Spanish+German, 10 take all three. How many take exactly two languages?
   

   Click for answer

   Exactly two = (French+Spanish - all3) + (French+German - all3) + (Spanish+German - all3) = $(40-10) + (30-10) + (20-10) = 30 + 20 + 10 = 60$.

Summary

Key takeaways:

• Two sets: $|A \cup B| = |A| + |B| - |A \cap B|$
• Three sets: add singles, subtract pairs, add triple
• General: alternating sum of intersections
• Derangements: $D_n = n! \sum (-1)^k/k! \approx n!/e$
• Always consider the complementary approach: count unwanted elements and subtract

Pitfalls

• Forgetting to add back the triple (and higher) intersections: The pattern alternates: add singles, subtract pairs, add triples, subtract quadruples, etc. Stopping after subtracting pair intersections gives the wrong result whenever triple intersections are nonempty. For $|A \cup B \cup C|$, omitting the $+|A \cap B \cap C|$ term undercounts because elements in all three sets were subtracted three times in the pair terms after being added three times in the singles — they net to 0 without the correction.
• Losing track of alternating signs in the general formula: The general Inclusion-Exclusion sum is $\sum_{k=1}^n (-1)^{k+1} \sum |\text{intersection of } k \text{ sets}|$. A sign error — using $(-1)^k$ instead of $(-1)^{k+1}$ — flips the entire formula. The mnemonic: start positive for singles, then alternate. For the complementary count $|A_1^c \cap \cdots \cap A_n^c|$, the formula uses $(-1)^k$ (without the $+1$), since it's $|U| - |\cup A_i|$.
• Computing intersection sizes incorrectly in divisibility problems: For $|A_i \cap A_j|$ where $A_i$ = multiples of $p_i$, the intersection is multiples of $\operatorname{lcm}(p_i, p_j)$, NOT $p_i \times p_j$. For example, multiples of 6 AND 10: the intersection is multiples of $\operatorname{lcm}(6, 10) = 30$, not 60. Using the product instead of the lcm overcounts the intersection and produces wrong results. This error compounds with more sets.
• Applying Inclusion-Exclusion when the complementary approach is massively simpler: If only a few elements satisfy NONE of the conditions, count those directly instead of applying the full machinery. "How many 5-letter strings contain at least one vowel?" — total $26^5$, subtract all-consonant $21^5$. Using Inclusion-Exclusion on the five vowel conditions would require $2^5 - 1 = 31$ intersection terms. Always evaluate whether direct complement counting is easier.
• Misapplying the derangement formula by forgetting $D_n \approx n!/e$ is an approximation: $D_n = \lfloor n!/e + 1/2 \rfloor$ (exact via rounding), but $n!/e$ alone is not an integer for $n \geq 1$. For small $n$, the approximation is poor: $D_4 = 9$ while $4!/e \approx 8.83$. The exact formula $D_n = n! \sum_{k=0}^n (-1)^k/k!$ is simple enough for small $n$ — use the approximation only for asymptotic estimates.

Next Steps

Next up: 26-07-recurrence-relations.md — solving counting problems with recursive structure.