MGU Mathematics Series — Combinatorics
Part III: Advanced Counting and Combinatorial Proof
Inclusion-Exclusion · Forbidden Positions · Derangements · Probability
Chapter 7 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 7:
Inclusion-Exclusion
and Overlapping Structures

When categories overlap, addition alone overcounts. Inclusion-exclusion is the systematic method of correction — the mathematics of what happens at the boundary between cases.

■ Part III: Advanced Counting and Combinatorial Proof ■

■ 14 Sections  •  Chapter 7 of 14 ■

Follows Chapters 1–6  ·  Prepares students for Chapter 8: Pigeonhole Principle and Existence Arguments

Chapter 7 — Front Matter

Purpose and Overview

This chapter deepens the study of counting by confronting a problem that arises again and again in combinatorics: what happens when the cases in a counting problem overlap? Earlier chapters built tools for disjoint cases — situations where every outcome belongs to exactly one category. But many real counting problems involve categories that share elements. A student may be enrolled in both mathematics and computer science. A password may violate one rule or another or both. A schedule may conflict with multiple constraints at once.

When cases overlap, adding them together counts shared elements more than once. The remedy is a systematic method of correction called inclusion-exclusion. Inclusion-exclusion is not a single formula to memorize. It is a principle about how to correct overcounting by carefully adding and subtracting counts of overlapping sets.

This chapter develops inclusion-exclusion from its basic two-set form through three sets and introduces the general principle. It connects inclusion-exclusion to complementary counting, forbidden position problems, and derangements — one of the most elegant applications in combinatorics. It also explores inclusion-exclusion in probability and scheduling.

By the end of this chapter, students will understand why overcounting happens, how to detect it, and how to correct it systematically.

Opening Question

A university offers three clubs: a mathematics club, a computer science club, and a chess club. A survey records that 40 students belong to at least one club. The mathematics club has 20 members, the computer science club has 18 members, and the chess club has 15 members. Some students belong to two clubs, and some belong to all three.

Can you determine how many students belong to exactly one club? Simple addition overcounts — students in two clubs have been counted twice, and students in all three have been counted three times. Inclusion-exclusion provides the correction.

14Sections
10Objectives
11Key Terms
12+Worked Examples

Why This Chapter Matters

Counting overlapping categories is one of the most common practical challenges in discrete mathematics. Every field that involves classification, filtering, or categorizing data encounters this problem.

In data science and databases, queries often ask how many records satisfy condition A or condition B or both. In cryptography and security, restrictions on passwords, keys, or codes involve forbidden patterns that may overlap. In scheduling and operations research, conflicts between tasks or constraints often overlap in complex ways. In probability, the probability of at least one of several events occurring requires inclusion-exclusion to compute exactly. In algorithms, counting valid configurations while excluding those that violate one or more rules is a standard technique.

Understanding inclusion-exclusion builds the combinatorial fluency needed for these fields. It also prepares students for derangements, Stirling numbers, Möbius inversion in advanced combinatorics, and sieve methods in number theory.

Learning Objectives

  1. 1Explain why overlapping categories cause overcounting and describe the correction strategy.
  2. 2Apply inclusion-exclusion to count unions of two and three sets.
  3. 3Use the general inclusion-exclusion principle in introductory cases with four or more sets.
  4. 4Apply complementary counting combined with inclusion-exclusion to handle multiple restrictions.
  5. 5Solve forbidden-position counting problems using inclusion-exclusion.
  6. 6Define derangements and compute their count using the inclusion-exclusion formula.
  7. 7Apply the derangement recurrence relation and identify its combinatorial meaning.
  8. 8Apply inclusion-exclusion in probability problems involving finite sample spaces.
  9. 9Apply inclusion-exclusion in scheduling and data classification problems.
  10. 10Choose an appropriate inclusion-exclusion strategy and identify common errors.
Chapter 7 — Contents

Sections at a Glance

Sections 7.1 – 7.4
The Inclusion-Exclusion Principle
Overlap · Two Sets · Three Sets · General Formula
Section 7.1

Why Overlap Causes Counting Errors

Recall from Chapter 2 that the sum rule applies when the cases being counted are disjoint — when no outcome belongs to two cases at the same time. If you are choosing a fruit from a basket containing 5 apples or 3 oranges, and each item is either an apple or an orange but not both, then the number of choices is simply 5 + 3 = 8.

The problem arises when the cases are not disjoint. Suppose a student can earn bonus credit by completing a math project, a science project, or both. Suppose 12 students completed the math project and 9 completed the science project. How many students completed at least one project?

If you write 12 + 9 = 21, you are overcounting the students who completed both. Each of those students is counted once in the group of 12 and once again in the group of 9. To get the correct count, you must subtract the overlap.

The Core Problem: Double-Counting

When A and B overlap: |A| + |B| counts every element in A ∩ B exactly twice. Subtracting |A ∩ B| once restores the correct count.

|A ∪ B| = |A| + |B| − |A ∩ B|

The Key Question

Before adding any two counts, ask: can a single object belong to both categories at the same time? If yes, overlap is present and inclusion-exclusion is required. If no, the sum rule applies directly.

Practice 7.1Identifying Overlap
  1. A club has 15 members who play chess and 12 members who play checkers. A student says "there are 27 club members who play at least one game." What assumption is the student making? When would this be wrong?
  2. A list of 50 numbers contains 20 even numbers and 15 multiples of 3. Can these categories overlap? Give an example of a number in both categories.
  3. In each pair, state whether the two categories can overlap. Explain briefly.

    a. Prime numbers and even numbers (among positive integers)
    b. Divisible by 4 and divisible by 6
    c. Contains the letter 'a' and contains the letter 'e' (among words)
Section 7.2

Review of Inclusion-Exclusion for Two Sets

Let A and B be two finite sets drawn from some universal set U. The union A ∪ B is the set of all elements in A, in B, or in both. The intersection A ∩ B is the set of elements in both A and B simultaneously.

Inclusion-Exclusion — Two Sets
|A ∪ B| = |A| + |B| − |A ∩ B|

Why this works: Adding |A| and |B| counts every element in A only once, every element in B only once, and every element in A ∩ B twice. Subtracting |A ∩ B| once brings the intersection elements back to a count of one.

Venn diagram description: Draw two overlapping circles inside a rectangle representing the universal set. The left region (inside A but outside B) contains elements belonging only to A. The right region (inside B but outside A) contains elements belonging only to B. The central region is A ∩ B. The formula counts the left region once, the central region once (added twice, subtracted once), and the right region once.

Example 7.2.1
Counting Students in Two Language Classes
  • ProblemA class of 30 students was surveyed. 18 study French, 14 study Spanish, and 6 study both. How many study at least one language?
  • ThinkThe categories overlap — some students study both. Use inclusion-exclusion.
  • RepresentLet F = students studying French, S = students studying Spanish. |F| = 18, |S| = 14, |F ∩ S| = 6.
  • Count |F ∪ S| = |F| + |S| − |F ∩ S| = 18 + 14 − 6 = 26
  • CheckThe 6 students who study both were counted in both 18 and 14. Subtracting 6 once corrects this. The result 26 ≤ 30 (class size). Reasonable.
  • Interpret26 students study at least one of French or Spanish. The remaining 30 − 26 = 4 students study neither.
Answer: 26 students study at least one language. 4 study neither.
Example 7.2.2
Finding the Intersection from the Union
  • ProblemIn a group of 50 people, 30 have a driver's license, 20 have a passport, and 45 have at least one of the two. How many have both?
  • ThinkThe union is given. Rearrange the formula to find the intersection.
  • Represent|D| = 30, |P| = 20, |D ∪ P| = 45. Find |D ∩ P|.
  • Count |D ∪ P| = |D| + |P| − |D ∩ P| 45 = 30 + 20 − |D ∩ P| |D ∩ P| = 50 − 45 = 5
  • CheckLicense only: 30 − 5 = 25. Passport only: 20 − 5 = 15. Both: 5. Total with at least one: 25 + 15 + 5 = 45. ✓
  • Interpret5 people have both a driver's license and a passport.
Answer: 5 people have both documents.
Complementary Form

The number of elements in neither A nor B is: |U| − |A ∪ B| = |U| − |A| − |B| + |A ∩ B|. This complementary form is useful when the problem states a total and asks how many elements fail to satisfy either condition.

Practice 7.2Two-Set Inclusion-Exclusion
  1. |A| = 25, |B| = 18, |A ∩ B| = 7. Find |A ∪ B|.
  2. |A ∪ B| = 40, |A| = 28, |B| = 22. Find |A ∩ B|.
  3. 60 students: 35 play chess, 28 play checkers, 12 play both. How many play at least one?
  4. 80 employees: 50 use spreadsheets, 35 use presentation software, 20 use both. How many use neither?
  5. 100 words: 40 have five+ letters, 30 have repeated letters, 15 have both. How many have at least one property?
  6. A set has |U| = 70, |A| = 32, |B| = 27, |A ∩ B| = 11. How many elements are in neither A nor B?
Section 7.3

Inclusion-Exclusion for Three Sets

When three overlapping sets are involved, the correction requires more steps. Adding |A| + |B| + |C| counts elements in one set once, elements in two sets twice, and elements in all three sets three times. After subtracting the three pairwise intersections, elements in exactly two sets are corrected, but elements in all three have been subtracted too many times. Adding back the triple intersection corrects this final error.

Inclusion-Exclusion — Three Sets
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Why Each Element Is Counted Exactly Once

Element belongs to…AddedSubtractedAdded backNet count
Exactly one set (e.g., only A)1 time0 times0 times1
Exactly two sets (e.g., A ∩ B, not C)2 times1 time (in |A ∩ B|)0 times1
All three sets (A ∩ B ∩ C)3 times3 times1 time1
Example 7.3.1
Three Overlapping School Clubs
  • ProblemIn a school of 100 students: Math club has 35 members, Science club 30, History club 28. Math ∩ Science: 12. Math ∩ History: 10. Science ∩ History: 8. All three: 4. How many belong to at least one club?
  • RepresentLet M, S, H represent the three clubs.
  • Count |M ∪ S ∪ H| = 35 + 30 + 28 − 12 − 10 − 8 + 4 = 93 − 30 + 4 = 67
  • Check67 is less than 100 (the school's total). Each subtraction step reduces the overcounting from repeated membership. Plausible.
  • Interpret67 students belong to at least one club. The remaining 100 − 67 = 33 students belong to none.
Answer: 67 students in at least one club. 33 in none.
Example 7.3.2
Three Languages at a Conference
  • ProblemAmong 50 people: 20 speak English, 18 speak French, 15 speak Spanish. English ∩ French: 8. English ∩ Spanish: 6. French ∩ Spanish: 5. All three: 3. How many speak at least one?
  • Count |E ∪ F ∪ S| = 20 + 18 + 15 − 8 − 6 − 5 + 3 = 37
  • Interpret37 people speak at least one language. The remaining 50 − 37 = 13 speak none of these three.
Answer: 37 people speak at least one of the three languages.
Practice 7.3Three-Set Inclusion-Exclusion
  1. In a school of 150 students: 70 play soccer, 55 play basketball, 50 swim. 25 play soccer and basketball, 20 play soccer and swim, 18 play basketball and swim, 8 do all three. How many participate in at least one activity?
  2. Using the data from Problem 1, find how many students participate in exactly one activity. (Hint: compute each region of the Venn diagram from the center outward.)
  3. Among 200 database records: 90 have tag A, 80 have tag B, 70 have tag C. 35 have A and B, 30 have A and C, 25 have B and C, 10 have all three. How many records have none of these tags?
  4. How many integers from 1 to 60 are divisible by 2, 3, or 5? (Use |A ∩ B| = multiples of lcm(a,b).)
  5. How many integers from 1 to 200 are divisible by 4, 6, or 10?
Section 7.4

General Inclusion-Exclusion as an Introduction

For any finite collection of sets A₁, A₂, …, Aₙ, the general inclusion-exclusion principle states: add the sizes of all individual sets, subtract the sizes of all pairwise intersections, add the sizes of all triple intersections, and continue alternating signs until the n-fold intersection is reached.

General Inclusion-Exclusion Principle
|A₁ ∪ A₂ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| − … + (−1)ⁿ⁻¹ |A₁ ∩ A₂ ∩ … ∩ Aₙ|

The alternating-sign structure is an algebraic consequence of the binomial theorem — an element in exactly k sets contributes C(k,1) − C(k,2) + C(k,3) − … = 1 to the total, so every element in the union is counted exactly once.

Scope note: In this textbook, most problems involve two or three sets. The four-set case appears in some applications and challenge problems. Problems involving five or more sets are typically encountered in advanced combinatorics beyond the scope of this chapter.

Example 7.4.1
Four Conditions — Divisibility by 2, 3, 5, or 7
  • ProblemHow many integers from 1 to 100 are divisible by 2, 3, 5, or 7?
  • RepresentLet A₂, A₃, A₅, A₇ be sets of multiples of 2, 3, 5, 7 in the range 1–100. Use ⌊100/k⌋ for multiples of k.
  • Count Singles: |A₂|=50, |A₃|=33, |A₅|=20, |A₇|=14. Sum: 117 Pairs: ⌊100/6⌋=16, ⌊100/10⌋=10, ⌊100/14⌋=7, ⌊100/15⌋=6, ⌊100/21⌋=4, ⌊100/35⌋=2. Sum: 45 Triples: ⌊100/30⌋=3, ⌊100/42⌋=2, ⌊100/70⌋=1, ⌊100/105⌋=0. Sum: 6 Quadruple: ⌊100/210⌋ = 0 Total: 117 − 45 + 6 − 0 = 78
  • Interpret78 integers from 1 to 100 are divisible by at least one of 2, 3, 5, or 7. The remaining 22 are divisible by none of these.
Answer: 78 integers are divisible by 2, 3, 5, or 7.
Practice 7.4General Principle
  1. In your own words, explain why the signs in inclusion-exclusion alternate between addition and subtraction.
  2. How many integers from 1 to 120 are divisible by 2, 3, or 5? Show your work for all individual sets, pairs, and the triple intersection.
  3. State whether the following claim is true or false: "For two disjoint sets A and B, inclusion-exclusion gives the same result as simple addition." Explain why.
Sections 7.5 – 7.8
Complements, Forbidden Positions, and Derangements
Restrictions · Forbidden Positions · Derangements · The D_n Formula
Section 7.5

Counting Complements with Restrictions

Many counting problems are easier to approach from the complement. Rather than directly counting the objects that satisfy a restriction, count all objects that violate it and subtract from the total.

When multiple restrictions are involved, the complement becomes a union of sets, each corresponding to a different restriction. Inclusion-exclusion computes that union.

Complementary Counting with Inclusion-Exclusion

Let U = all objects with no restrictions. Let A₁, A₂, …, Aₖ = sets of objects violating each restriction.

Objects violating none of the restrictions = |U| − |A₁ ∪ A₂ ∪ … ∪ Aₖ|

Apply inclusion-exclusion to compute the union, then subtract from |U|.

Example 7.5.1
Counting Integer Solutions with Upper Bounds
  • ProblemHow many non-negative integer solutions does x₁ + x₂ + x₃ = 10 have if x₁ ≤ 4, x₂ ≤ 4, and x₃ ≤ 4?
  • ThinkStars and bars gives the unrestricted count; inclusion-exclusion removes solutions that violate the upper bounds.
  • RepresentUnrestricted solutions: C(12,2) = 66. Let Aᵢ = solutions where xᵢ ≥ 5. Substitute yᵢ = xᵢ − 5 to count each Aᵢ.
  • Count |A₁|: y₁ + x₂ + x₃ = 5 → C(7,2) = 21. Similarly |A₂| = |A₃| = 21. |A₁ ∩ A₂|: y₁ + y₂ + x₃ = 0 → 1 solution. Similarly |A₁ ∩ A₃| = |A₂ ∩ A₃| = 1. |A₁ ∩ A₂ ∩ A₃|: would need sum ≥ 15, but total is 10. → 0. |A₁ ∪ A₂ ∪ A₃| = 21+21+21 − 1−1−1 + 0 = 60 Valid solutions = 66 − 60 = 6
  • CheckList the 6 valid solutions: (2,4,4), (4,2,4), (4,4,2), (3,3,4), (3,4,3), (4,3,3). That is exactly 6. ✓
  • InterpretThere are exactly 6 non-negative integer solutions with each variable at most 4.
Answer: 6 solutions.
Practice 7.5Complement and Restrictions
  1. How many 4-character strings from {0,1,2,3,4,5} (repetition allowed) contain neither 0 nor 5?
  2. How many non-negative integer solutions does x₁ + x₂ + x₃ = 12 have if x₁ ≤ 5 and x₂ ≤ 5? (No restriction on x₃.)
  3. How many non-negative integer solutions does x₁ + x₂ + x₃ + x₄ = 8 have if each variable is at most 3?
Section 7.6

Forbidden Position Problems

A forbidden position problem asks: in how many ways can objects be arranged so that none of them occupies a forbidden position? These problems arise in scheduling (a task must not be assigned to a certain slot), seating (two people must not sit in specific seats), and code construction.

General Approach for Forbidden Positions

1. Let U = all arrangements with no restrictions.

2. For each forbidden condition i, let Aᵢ = arrangements where condition i is violated.

3. Valid arrangements = |U| − |A₁ ∪ A₂ ∪ … ∪ Aₖ|

Apply inclusion-exclusion to compute the union of violation sets.

Example 7.6.1
Seating with Forbidden Chairs
  • ProblemFour people — Alice, Bob, Carol, and David — are seated in a row of 4 chairs. Alice must not sit in chair 1, Bob must not sit in chair 2, and Carol must not sit in chair 3. How many valid seating arrangements are there?
  • Represent|U| = 4! = 24. Let A = Alice in chair 1, B = Bob in chair 2, C = Carol in chair 3.
  • Count |A| = |B| = |C| = 3! = 6 (one person fixed, 3 others free) |A ∩ B| = |A ∩ C| = |B ∩ C| = 2! = 2 (two people fixed) |A ∩ B ∩ C| = 1! = 1 (three people fixed) |A ∪ B ∪ C| = 6+6+6 − 2−2−2 + 1 = 13 Valid arrangements = 24 − 13 = 11
  • InterpretThere are 11 valid seating arrangements.
Answer: 11 valid arrangements.
Example 7.6.2
Forbidden Digit Positions in a Code — Verified by Listing
  • ProblemA three-digit code uses the digits 1, 2, 3 in some order (each used exactly once). The digit 1 may not be in position 1, and the digit 2 may not be in position 2. How many valid codes are there?
  • Represent|U| = 3! = 6. Let A = codes with 1 in position 1. Let B = codes with 2 in position 2.
  • Count |A| = 2! = 2. |B| = 2! = 2. |A ∩ B| = 1. |A ∪ B| = 2 + 2 − 1 = 3 Valid codes = 6 − 3 = 3
  • CheckAll 6 permutations: 123 ✗ (1 in pos 1), 132 ✗ (1 in pos 1), 213 ✗ (2 in pos 2), 231 ✓, 312 ✓, 321 ✓. Exactly 3 valid codes. ✓
  • InterpretThe three valid codes are 231, 312, and 321.
Answer: 3 valid codes.
Practice 7.6Forbidden Position Problems
  1. Four people are assigned to four roles. Person 1 cannot take role 1, person 2 cannot take role 2, person 3 cannot take role 3. (Person 4 has no restriction.) How many valid assignments are there?
  2. Five letters A, B, C, D, E are arranged in a row. A cannot be first, and E cannot be last. How many valid arrangements are there?
  3. Six books are placed on a shelf. Book 1 cannot go in position 1, and book 2 cannot go in position 2. How many valid arrangements are there?
Section 7.7

Derangements

A derangement is a permutation of n objects in which no object appears in its original position. In other words, every object is displaced from where it started.

Derangements arise naturally in problems like: a group of people swap gifts so that each person receives a gift that is not their own; a set of letters is misaddressed so that each letter goes to the wrong envelope; a matching problem where each element must be paired with a different element than its original partner.

The number of derangements of n objects is denoted D_n.

Example 7.7.1
Small Cases — Listing Derangements
  • n = 1Only one permutation: (1). Element 1 is in position 1. No derangements exist. D₁ = 0.
  • n = 2Permutations: (1,2) and (2,1). Only (2,1) displaces both elements. D₂ = 1.
  • n = 3All 6 permutations of {1,2,3}: (1,2,3) ✗, (1,3,2) ✗, (2,1,3) ✗, (2,3,1) ✓, (3,1,2) ✓, (3,2,1) ✗. D₃ = 2.
  • Note(3,2,1) is NOT a derangement — element 2 is still in position 2. Always check every element.
D₁ = 0, D₂ = 1, D₃ = 2.

Setting Up the Inclusion-Exclusion for Derangements

For each i from 1 to n, let Aᵢ = the set of permutations in which element i is in position i (element i is "fixed"). The number of derangements is the number of permutations with no fixed points:

D_n = n! − |A₁ ∪ A₂ ∪ … ∪ Aₙ|

Key Observation for the Derivation

|Aᵢ| = (n−1)! — fixing element i leaves n−1 elements free to arrange.

|Aᵢ ∩ Aⱼ| = (n−2)! — fixing two elements leaves n−2 free.

Intersection of any k sets = (n−k)!

Number of ways to choose k sets from n: C(n,k)

So the sum over all k-element subsets: C(n,k)·(n−k)! = n!/k!

Sections 7.8 – 7.11
The Derangement Formula, Probability, and Applications
D_n Formula · Recurrence · Probability · Scheduling · Data Classification
Section 7.8

The Derangement Formula

The Derangement Formula
D_n = n! · Σ (−1)ᵏ / k! for k = 0 to n = n!(1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!)

Verification for Small Values

D₁ = 1!(1 − 1) = 0. ✓

D₂ = 2!(1 − 1 + 1/2) = 2 · 1/2 = 1. ✓

D₃ = 3!(1 − 1 + 1/2 − 1/6) = 6 · 1/3 = 2. ✓

D₄ = 4!(1 − 1 + 1/2 − 1/6 + 1/24) = 24 · 3/8 = 9. ✓

Derangement Count Table

nn!D_nD_n / n! (approx.)
1100.000
2210.500
3620.333
42490.375
5120440.367
67202650.368
Observation

The ratio D_n / n! stabilizes near 0.368 as n grows. This is the fraction of all permutations that are derangements. For large n, roughly 1 in e ≈ 2.718 permutations is a derangement — a fact explored in advanced combinatorics.

The Derangement Recurrence

The derangement numbers also satisfy a recurrence. For n ≥ 2:

Derangement Recurrence
D_n = (n − 1)(D_{n−1} + D_{n−2})

Combinatorial interpretation: Element 1 goes to some position j ≠ 1 (n−1 choices). Then either element j goes to position 1 (a "swap"), reducing the problem to deranging n−2 elements (D_{n−2} ways), or element j does not go to position 1, reducing to deranging n−1 elements (D_{n−1} ways). Hence D_n = (n−1)(D_{n−1} + D_{n−2}).

Example 7.8.1
Gift Swap Among Five Friends
  • ProblemFive friends exchange holiday gifts. Each person must receive a gift from someone other than themselves. How many ways can the gifts be distributed?
  • Count D₅ = 5!(1 − 1 + 1/2 − 1/6 + 1/24 − 1/120) = 120 · 44/120 = 44
  • Verify with recurrence D₄ = 3(D₃ + D₂) = 3(2 + 1) = 9 ✓ D₅ = 4(D₄ + D₃) = 4(9 + 2) = 44 ✓
  • InterpretThere are 44 ways to distribute the gifts so nobody receives their own.
Answer: D₅ = 44 valid gift distributions.
Example 7.8.2
Permutations with Exactly k Fixed Points
  • ProblemHow many permutations of four letters A, B, C, D have exactly 2 letters in their original positions?
  • ThinkChoose which 2 letters remain fixed, then derange the remaining 2.
  • Count C(4,2) · D₂ = 6 · 1 = 6
  • Interpret6 permutations of A, B, C, D have exactly 2 letters in their original positions.
Answer: 6 permutations with exactly 2 fixed points.
Permutations with Exactly k Fixed Points

The number of permutations of n objects with exactly k fixed points is:

C(n, k) · D_{n−k}

Choose which k elements are fixed, then derange the remaining n−k.

Practice 7.8Derangements
  1. Compute D₆ using the recurrence from D₄ = 9 and D₅ = 44.
  2. Verify D₄ = 9 by fully expanding the formula.
  3. How many ways can 6 people exchange gifts so nobody receives their own?
  4. How many permutations of {1,2,3,4,5} have exactly one fixed point?
  5. How many permutations of {1,2,3,4} have exactly two fixed points?
  6. How many permutations of {1,2,3,4,5} have no fixed points among the first three elements and no restriction on the last two?
Section 7.9

Inclusion-Exclusion in Probability

Inclusion-exclusion has a natural interpretation in probability. If A and B are events in a finite probability space where all outcomes are equally likely, then the probability formula follows directly from dividing the set-count formula through by the total number of outcomes.

Probability — Inclusion-Exclusion
P(A ∪ B) = P(A) + P(B) − P(A ∩ B) P(A ∪ B ∪ C) = P(A) + P(B) + P(C) − P(A ∩ B) − P(A ∩ C) − P(B ∩ C) + P(A ∩ B ∩ C)
Example 7.9.1
Drawing a Face Card or a Club
  • ProblemOne card is drawn from a standard deck of 52. What is the probability that the card is a face card (Jack, Queen, or King) or a club?
  • RepresentLet F = event of drawing a face card, C = event of drawing a club. |F| = 12, |C| = 13, |F ∩ C| = 3 (Jack, Queen, King of clubs).
  • Count |F ∪ C| = 12 + 13 − 3 = 22 P(F ∪ C) = 22/52 = 11/26
  • InterpretThe probability of drawing a face card or a club is 11/26.
Answer: 11/26.
Example 7.9.2
At Least One Defective Item
  • ProblemA box contains 10 items, 3 of which are defective. Two items are selected at random without replacement. What is the probability that at least one is defective?
  • ThinkUse the complement — it is easier to count "no defectives" and subtract.
  • Count Total ways to choose 2 from 10: C(10,2) = 45 Ways to choose 2 non-defective from 7: C(7,2) = 21 P(no defectives) = 21/45 = 7/15 P(at least one defective) = 1 − 7/15 = 8/15
  • InterpretThere is an 8/15 probability that at least one selected item is defective.
Answer: 8/15.
MGU Library Connection
  • The probability form of inclusion-exclusion is used extensively in the MGU Probability and Statistics textbook, Chapters 3 and 4 on compound events and conditional probability.
  • Students studying data science and machine learning mathematics will encounter inclusion-exclusion in Bayesian reasoning and classifier evaluation.
  • The non-uniform (weighted) version of these probability formulas appears in MGU Probability and Statistics, Chapter 5.
Practice 7.9Inclusion-Exclusion in Probability
  1. A die is rolled twice. What is the probability that the first roll is 6 or the sum of both rolls is 7?
  2. A bag contains 15 cards numbered 1 to 15. One card is drawn at random. What is the probability that the number is even or divisible by 3?
  3. In a class of 30 students, each has an equal probability of being selected. 18 study French, 14 study Spanish, and 6 study both. If one student is selected at random, what is the probability that they study at least one of French or Spanish?
  4. Two dice are rolled. What is the probability that neither die shows a 4?
Section 7.10

Inclusion-Exclusion in Scheduling

Scheduling problems often require assigning tasks to time slots, people to shifts, or resources to projects, subject to constraints that forbid certain assignments. When two or more constraints can be simultaneously violated, inclusion-exclusion is needed to count valid schedules.

Example 7.10.1
Assigning Workers to Shifts with Restrictions
  • ProblemA manager assigns 4 workers (Alice, Bob, Carol, David) to 4 different shifts (morning, afternoon, evening, night), one per shift. Alice refuses to work mornings, and Bob refuses to work nights. How many valid schedules are there?
  • Represent|U| = 4! = 24. Let A = Alice in morning, B = Bob in night.
  • Count |A| = 3! = 6. |B| = 3! = 6. |A ∩ B| = 2! = 2. |A ∪ B| = 6 + 6 − 2 = 10 Valid schedules = 24 − 10 = 14
  • InterpretThere are 14 valid scheduling assignments.
Answer: 14 valid schedules.
Practice 7.10Scheduling
  1. Five workers are assigned to five shifts. Worker A refuses shifts 1 and 2, worker B refuses shift 3 (no other restrictions). How many valid assignments are there?
  2. Three people are assigned to three tasks. Person 1 refuses task 1, person 2 refuses task 2. How many valid assignments are there? Verify by listing.
Section 7.11

Inclusion-Exclusion in Data Classification

Data classification problems arise frequently in computing and data science. Given a dataset, how many records satisfy at least one criterion? How many satisfy none? How many satisfy exactly one? These are union, complement, and region-counting problems solved by inclusion-exclusion.

Example 7.11.1
Customer Purchase Categories
  • ProblemA database has 200 customer records. 80 purchased electronics (E), 70 purchased clothing (C), 60 purchased books (B). E ∩ C: 30, E ∩ B: 25, C ∩ B: 20, all three: 10. Find (a) at least one category, (b) no category, (c) exactly one category.
  • Count (a) |E ∪ C ∪ B| = 80+70+60 − 30−25−20 + 10 = 145
  • Count (b) 200 − 145 = 55 customers purchased none of the three.
  • Count (c) Only E: 80 − 30 − 25 + 10 = 35 Only C: 70 − 30 − 20 + 10 = 30 Only B: 60 − 25 − 20 + 10 = 25 Total exactly one: 35 + 30 + 25 = 90
  • NoteFill in a Venn diagram from the center outward: start with the triple intersection (10), then compute each pair-only region, then each single-only region.
Answer: (a) 145 purchased at least one. (b) 55 purchased none. (c) 90 purchased exactly one.
MGU Library Connection
  • Inclusion-exclusion in database queries connects to the MGU Data Science Foundations textbook chapters on filtering, joining, and aggregating records.
  • The Boolean logic of SQL WHERE clauses reflects the same set-theoretic structure as inclusion-exclusion.
  • Students in the MGU Algorithms course will see inclusion-exclusion used to count valid configurations in constraint-satisfaction problems.
Practice 7.11Data Classification
  1. A research dataset has 300 articles. 120 are tagged "biology," 90 "chemistry," 60 "physics." 35 are biology ∩ chemistry, 25 are biology ∩ physics, 20 are chemistry ∩ physics, and 8 are all three. How many articles are tagged in exactly one category?
  2. Using the data above: how many articles are tagged in exactly two categories?
  3. A Venn diagram for three sets has seven regions. For Example 7.11.1, compute the count in each of the seven regions and confirm they sum to 145.
Sections 7.12 – 7.14
Strategy, Common Mistakes, and Looking Ahead
Decision Guide · Eight Common Errors · Preparing for Existence Arguments
Section 7.12

Choosing an Inclusion-Exclusion Strategy

Knowing when and how to apply inclusion-exclusion requires recognizing the structure of the problem. Use the following decision guide before applying any formula.

1
Identify whether categories overlap. Ask: can a single object belong to two or more categories at the same time? If yes, overlap is present and the sum rule is insufficient. If no, the sum rule applies directly.
2
Decide whether to count the union directly or use the complement. If the problem asks "how many satisfy at least one condition," compute |A₁ ∪ … ∪ Aₖ| using inclusion-exclusion. If the problem asks "how many satisfy none of the forbidden conditions," compute |U| − |A₁ ∪ … ∪ Aₖ| where each Aᵢ represents a violation.
3
Identify all intersections needed. For two sets: |A|, |B|, |A ∩ B|. For three sets: all three individual counts, all three pairwise counts, and the triple intersection. List all needed intersections systematically before computing.
4
Verify the signs. Single sets: added (+). Pairwise intersections: subtracted (−). Triple intersections: added (+). The sign alternates: +, −, +, −, …
5
Check against boundary conditions. The result must be a non-negative integer not exceeding |U|. A negative result or a result larger than the universal set signals an error in setup or computation.
Problem TypeBest Approach
"How many satisfy at least one condition?"Compute |A₁ ∪ … ∪ Aₖ| directly via inclusion-exclusion.
"How many satisfy none of the conditions?"Use complement: |U| − |A₁ ∪ … ∪ Aₖ|.
"No object in its original position?"Derangement formula: D_n.
"Exactly k fixed points?"C(n,k) · D_{n−k}.
Symmetric restrictions (all sets same size)Use the symmetric form: Σ(−1)ᵏ C(n,k) · f(k).
Section 7.13

Common Inclusion-Exclusion Mistakes

Mistake 1 — Adding Overlapping Categories Without Subtracting
"12 students in Math and 9 in Science → 21 students total."

Unless the problem explicitly states that the sets are disjoint, you cannot assume they are. Any student enrolled in both has been counted twice. Always ask whether the categories can overlap before adding.

Mistake 2 — Confusing AND with OR
Using the formula to find |A ∩ B| instead of |A ∪ B|.

The inclusion-exclusion formula gives |A ∪ B| — the count for "A OR B or both." To find |A ∩ B|, rearrange the formula: |A ∩ B| = |A| + |B| − |A ∪ B|.

Mistake 3 — Wrong Signs
Subtracting pairwise intersections then also subtracting the triple intersection.

The formula always begins with addition of individual sets and alternates: add singles, subtract pairs, add triples. Never subtract the triple intersection.

Mistake 4 — Computing Intersections as Products
|Aᵢ ∩ Aⱼ| = |Aᵢ| · |Aⱼ|

An intersection is not a product. |Aᵢ ∩ Aⱼ| counts objects satisfying both conditions simultaneously — computed directly from the structure of the problem, not by multiplying individual set sizes.

Mistake 5 — Omitting the Triple Intersection
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C|

For three sets, all four terms are required. Omitting + |A ∩ B ∩ C| underestimates the union by the size of the triple intersection.

Mistake 6 — Confusing "Exactly One" with "At Least One"
Computing |A ∪ B| when the problem asks for exactly one set only.

"Exactly one" requires a separate calculation. For two sets: |A| + |B| − 2|A ∩ B|. For three sets: fill in the Venn diagram region by region from the center outward.

Mistake 7 — Simple Subtraction Instead of the Derangement Formula
D_n = n! − n

Derangements require the full inclusion-exclusion formula. The count D_n = n! Σ (−1)ᵏ/k! is not a simple subtraction. Subtracting only n accounts for just the case where one element is fixed, ignoring overcounting in intersections.

Mistake 8 — Applying D_n to Non-Derangement Problems
Using D_n whenever a "displacement" or "wrong position" problem appears.

D_n counts permutations with NO fixed points at all, where the forbidden position of each element is specifically its own original position. If fixed points are allowed, or if the forbidden positions are not each element's original position, use the general forbidden-position approach instead.

Section 7.14

Preparing for Pigeonhole and Existence Arguments

Inclusion-exclusion has been a tool for exact counting: it produces a precise number of objects satisfying or violating conditions. But some combinatorial problems do not ask for exact counts. They ask: must some particular structure exist?

In Chapter 8, the central question shifts from "how many?" to "must at least one?" This is the realm of existence arguments. The most famous is the Pigeonhole Principle: if more pigeons are placed into fewer holes than there are pigeons, at least one hole must contain at least two pigeons. The applications are remarkably powerful — far beyond what this simple statement suggests.

The connection to inclusion-exclusion is conceptual. Both techniques reason about overlapping or constrained distributions of objects. Inclusion-exclusion counts exactly; the Pigeonhole Principle proves that a particular overlap must occur, even without knowing where.

Students should carry these ideas from Chapter 7 into Chapter 8: sets and their intersections; the idea that when objects are distributed into categories, overlaps may be forced; complementary reasoning (proving something exists by assuming it does not and reaching a contradiction); and the structure of counting arguments as tools for proving general facts, not just individual calculations.

Chapter 7 — Back Matter

Chapter Summary

Key Terms Review

union
A ∪ B: the set of all elements in at least one of the given sets. Counted by inclusion-exclusion when sets overlap.
intersection
A ∩ B: the set of elements belonging to all of the given sets simultaneously. The key quantity in correction formulas.
complement
Ā or Aᶜ: elements in the universal set not in A. Used in the "subtract from total" strategy.
disjoint sets
Sets with no elements in common. Their union is their sum; no correction needed.
overcounting
The error of counting some elements more than once, which occurs when overlapping sets are simply added.
inclusion-exclusion
The formula for |A₁ ∪ … ∪ Aₙ| using alternating sums of intersection sizes. The central method of this chapter.
forbidden position
A counting problem in which each object is prohibited from one or more specific positions.
derangement
A permutation in which no element occupies its original position. Every element is displaced.
D_n
The number of derangements of n objects. D_n = n! Σ (−1)ᵏ/k!, with recurrence D_n = (n−1)(D_{n−1} + D_{n−2}).
fixed point
An element that occupies its original position in a permutation. A derangement has no fixed points.
complementary counting
Finding a count by subtracting the unwanted cases from the total: valid = |U| − |violations|.

Concept Review Questions

  1. What is the difference between disjoint sets and overlapping sets? Give an example of each.
  2. Why does adding |A| and |B| overcount |A ∪ B| when the sets overlap?
  3. In the three-set formula, why is the triple intersection added back rather than subtracted?
  4. Explain what it means for a problem to have "overlapping restrictions." Give a real-world example.
  5. What is a derangement? List all derangements of {1, 2, 3}.
  6. What is the relationship between the derangement count D_n and the full inclusion-exclusion setup? Explain in words how the formula is derived.
  7. Explain in words why P(A ∪ B) = P(A) + P(B) − P(A ∩ B) follows from inclusion-exclusion for sets.
  8. When would you use the complement method instead of computing the union directly?
  9. A student says: "I can count elements in exactly two of three sets by computing |A ∩ B| + |A ∩ C| + |B ∩ C|." Is this correct? Explain why or why not.
  10. What is the pattern of signs in the inclusion-exclusion formula for n sets? Why does it alternate?

Skill Practice

Part ATwo-Set Inclusion-Exclusion
  1. |A| = 25, |B| = 18, |A ∩ B| = 7. Find |A ∪ B|.
  2. |A ∪ B| = 36, |A| = 25, |B| = 18. Find |A ∩ B|.
  3. |U| = 50, |A| = 32, |B| = 27, |A ∩ B| = 11. How many elements are in neither A nor B?
  4. 60 students: 35 play chess, 28 play checkers, 12 play both. How many play at least one?
  5. 80 employees: 50 use spreadsheets, 35 use presentation software, 20 use both. How many use neither?
Part BThree-Set Inclusion-Exclusion
  1. 70 play soccer, 55 basketball, 50 swim. 25 play two first, 20 first and third, 18 second and third, 8 all three. At least one?
  2. Using Part B Problem 1: how many participate in exactly one activity?
  3. 200 records: tags A (90), B (80), C (70). A∩B: 35, A∩C: 30, B∩C: 25, all three: 10. How many have no tags?
  4. Integers 1–60 divisible by 2, 3, or 5. Count using inclusion-exclusion.
  5. Integers 1–200 divisible by 4, 6, or 10.
Part CForbidden Positions and Derangements
  1. 4 workers, 4 shifts: Alice refuses shift 1, Bob refuses shift 4. Valid schedules?
  2. 5 letters arranged in a row: A cannot be first, E cannot be last. Valid arrangements?
  3. Compute D₅ using the formula.
  4. Compute D₆ using the recurrence from D₄ = 9 and D₅ = 44.
  5. How many permutations of {1,2,3,4,5} have exactly one fixed point?
  6. How many permutations of {1,2,3,4} have no fixed points?
Part DProbability
  1. P(A) = 3/8, P(B) = 1/4, P(A ∩ B) = 1/8. Find P(A ∪ B).
  2. One card drawn from 52: P(heart or face card)?
  3. Numbers 1–20: P(even or divisible by 3)?
  4. Box of 12 items, 4 defective. 3 selected without replacement. P(at least one defective)?
  5. Die rolled twice: P(first roll even OR sum equals 8)?

Proof and Reasoning

  1. Prove the two-set inclusion-exclusion formula by tracking the count of each type of element: those in only A, those in only B, and those in A ∩ B.
  2. Derive the three-set formula using the two-set formula applied first to A and then to (B ∪ C).
  3. Prove D₁ = 0 and D₂ = 1 directly from the definition by listing all permutations.
  4. Show that the number of permutations of n elements with exactly k fixed points is C(n,k) · D_{n−k}. Explain the combinatorial reasoning.
  5. The formula for elements in exactly one of two sets A and B is |A| + |B| − 2|A ∩ B|. Derive this from the inclusion-exclusion formula and the region structure of a Venn diagram.
  6. Verify that D₄ = 9 by fully expanding the formula D₄ = 4! Σ (−1)ᵏ/k! for k = 0 to 4.
  7. Explain in words why the recurrence D_n = (n−1)(D_{n−1} + D_{n−2}) holds. Your explanation should refer to where element 1 goes and what happens to element j.

Applications

  1. Data classification: A research dataset has 300 articles: 120 tagged "biology," 90 "chemistry," 60 "physics." 35 are biology ∩ chemistry, 25 are biology ∩ physics, 20 are chemistry ∩ physics, and 8 are all three. How many articles are tagged in exactly one category?
  2. Scheduling: Seven workers are assigned to seven shifts. Worker A refuses shifts 1 and 2, worker B refuses shift 3. How many valid assignments are there? (Apply inclusion-exclusion for three forbidden conditions.)
  3. Probability: A die is rolled twice. What is the probability that the sum is less than 5 or the sum is greater than 9? (Are these events mutually exclusive?)
  4. Integer solutions: How many non-negative integer solutions does x₁ + x₂ + x₃ + x₄ = 10 have if each variable is at most 4?
  5. Gift exchange: In a company of 8 employees, they hold a holiday gift exchange. How many ways can gifts be distributed so that no employee receives their own gift?
  6. Tournament: Six players enter a tournament where each player must be assigned to a different round (1 through 6). Player A cannot play in round 1, player B cannot play in round 2, and player C cannot play in round 6. How many valid tournament assignments exist?

Technology and Spreadsheet Practice

  1. Build a spreadsheet that computes D_n for n = 1 through n = 12 using the formula D_n = n! Σ (−1)ᵏ/k!. Verify D₄ = 9, D₅ = 44, and D₆ = 265.
  2. Extend the spreadsheet to compute the recurrence D_n = (n−1)(D_{n−1} + D_{n−2}) and confirm it matches the formula values for each row.
  3. Build a three-set inclusion-exclusion calculator: input the seven values (|A|, |B|, |C|, |A∩B|, |A∩C|, |B∩C|, |A∩B∩C|) and output |A ∪ B ∪ C|. Test it with the values from Examples 7.3.1 and 7.11.1.

Error Analysis

Each problem shows a student's work. Identify and explain each error, then provide the correct solution.

Error A

Problem: 50 students are enrolled in Algebra or Geometry. 30 are in Algebra and 25 are in Geometry. The student writes: "At least one means both are included, so the total is 30 + 25 = 55."

55

Identify the error and correct it. What additional information is needed?

Error B

Problem: How many integers from 1 to 30 are divisible by 2 or 3?

⌊30/2⌋ + ⌊30/3⌋ = 15 + 10 = 25

Identify the error and correct it.

Error C

Problem: Find |A ∪ B ∪ C| given |A|=12, |B|=10, |C|=8, |A∩B|=4, |A∩C|=3, |B∩C|=2, |A∩B∩C|=1.

12 + 10 + 8 − 4 − 3 − 2 − 1 = 20

Identify the error (one incorrect sign). State the correct answer.

Error D

Problem: How many permutations of 5 elements are derangements?

"There are 5! = 120 total permutations. Subtract the 5 permutations where one element is fixed. Answer: 115."

Identify the conceptual error. Apply the correct formula and state the right answer.

Error E

Problem: In a class of 30 students, 18 study French and 12 study Spanish. Find how many study exactly one language.

"Exactly one = |F ∪ S| − |F ∩ S| = (18 + 12 − |F ∩ S|) − |F ∩ S|"

The student's setup is partially correct. Explain what this expression actually computes. What formula correctly gives "exactly one"? Is any information missing?

Chapter 7 Checkpoint

Chapter 7 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 7
Part A — Concept
  1. State the inclusion-exclusion formula for two sets. Explain what each term counts and why the formula gives the correct count of |A ∪ B|.
  2. A student needs to count arrangements of 5 objects where none is in its original position. What type of counting problem is this? What formula applies?
  3. Describe a real-world scenario requiring three-set inclusion-exclusion. Identify the three sets and their intersections.
  4. Explain the difference between "at least one violation" and "exactly one violation." How does the count for each differ?
Part B — Skill
  1. In a group of 40 students, 22 play an instrument, 17 do sports, and 8 do both. How many do neither?
  2. Among 100 records: 50 have property A, 40 have B, 30 have C, 15 have A and B, 12 have A and C, 10 have B and C, 5 have all three. How many records have at least one property?
  3. How many integers from 1 to 120 are divisible by 3, 4, or 5?
  4. Compute D₄ using the formula. Verify using the recurrence with D₂ = 1 and D₃ = 2.
  5. Five people exchange gifts in a circle. How many exchanges result in nobody receiving their own gift?
  6. How many non-negative integer solutions does x₁ + x₂ + x₃ = 9 have if each variable is at most 4?
Part C — Reasoning and Application
  1. A bag contains 15 cards numbered 1 to 15. One card is drawn at random. What is the probability that the number is even or divisible by 3?
  2. Six people are seated in a row. Person A may not sit in seat 1, person B may not sit in seat 6, and person C may not sit in seat 3. How many valid arrangements are there?
  3. Modeling problem: A company of 10 employees holds a secret gift exchange. Using the derangement formula, compute D₁₀. Then compute what fraction of all 10! permutations are valid gift exchanges. Express this fraction as a decimal rounded to four places.
Looking Ahead
Chapter 8: Pigeonhole Principle and Existence Arguments

Chapter 7 gave you a powerful tool for exact counting — inclusion-exclusion corrects overcounting by systematically adding and subtracting overlapping set sizes. Chapter 8 introduces a completely different kind of question: not "how many?" but "must this happen?" The Pigeonhole Principle proves that when objects are distributed into categories under certain conditions, some particular arrangement is inevitable. No construction is needed, only counting and reasoning. Students who have mastered inclusion-exclusion — especially the ideas of sets, distributions, and forced overlaps — are well prepared for this next step.

MGU Library Connection
  • Discrete Mathematics: Set Theory and Boolean Logic — foundational context for union, intersection, and complement.
  • Probability and Statistics, Chapters 3–4: The addition rule for compound events and conditional probability using inclusion-exclusion.
  • Algorithms: Counting valid configurations for constraint-satisfaction problems using complementary counting.
  • Cryptography: Counting valid permutation ciphers using derangements and forbidden-position arguments.
  • Data Science Foundations: Filtering and aggregating database records with Boolean query logic.
  • Operations Research: Scheduling under constraints — inclusion-exclusion as a tool for valid assignment counts.
  • Advanced Combinatorics preview: The Principle of Inclusion-Exclusion in graph coloring, the chromatic polynomial, and the Möbius function in number theory.