The Central Idea
Suppose two finite sets \(A\) and \(B\) overlap.
If we add
\[ |A|+|B|, \]every element in \(A\cap B\) is counted twice.
To correct the double count, subtract the overlap once:
\[ \boxed{|A\cup B|=|A|+|B|-|A\cap B|}. \]Why Simple Addition Can Fail
Suppose \(18\) students study French and \(14\) study Spanish.
If \(6\) students study both languages, then
\[ 18+14=32 \]counts those \(6\) students twice.
Subtract the duplicate count:
\[ 18+14-6=26. \]Therefore,
\[ \boxed{26} \]students study French or Spanish.
The Two-Set Formula
For finite sets \(A\) and \(B\),
\[ \boxed{|A\cup B|=|A|+|B|-|A\cap B|}. \]The formula has three steps:
- include all elements of \(A\);
- include all elements of \(B\);
- exclude one copy of the overlap \(A\cap B\).
Connection to the Sum Principle
If \(A\) and \(B\) are disjoint, then
\[ A\cap B=\varnothing \]and
\[ |A\cap B|=0. \]The inclusion–exclusion formula becomes
\[ |A\cup B|=|A|+|B|. \]Thus, the ordinary sum principle is the zero-overlap case of inclusion–exclusion.
Example: Divisibility by 2 or 3
How many integers from \(1\) through \(30\) are divisible by \(2\) or \(3\)?
Let
\[ A=\{\text{multiples of }2\} \]and
\[ B=\{\text{multiples of }3\}. \]There are
\[ |A|=15 \]multiples of \(2\), and
\[ |B|=10 \]multiples of \(3\).
Numbers divisible by both \(2\) and \(3\) are multiples of \(6\):
\[ |A\cap B|=5. \]Therefore,
\[ \boxed{15+10-5=20}. \]“Or” Usually Means Union
In counting problems, a condition such as
\[ \text{“property }A\text{ or property }B\text{”} \]often corresponds to
\[ A\cup B. \]If the properties can occur together, inclusion–exclusion may be needed.
Inclusive “Or”
In mathematics, “\(A\) or \(B\)” normally includes outcomes satisfying both \(A\) and \(B\), unless the problem explicitly says “but not both” or “exactly one.”
Thus,
\[ A\cup B \]includes
\[ A\cap B. \]Exactly One of Two Properties
Suppose we want outcomes that satisfy exactly one of \(A\) or \(B\).
Start with
\[ |A|+|B|. \]An element in \(A\cap B\) appears twice, but for “exactly one” it should appear zero times.
Therefore, subtract the overlap twice:
\[ \boxed{|A|+|B|-2|A\cap B|}. \]Example: Exactly One Club
Suppose \(25\) students belong to the mathematics club, \(17\) belong to the science club, and \(8\) belong to both.
The number belonging to exactly one club is
\[ 25+17-2(8)=26. \]Therefore,
\[ \boxed{26} \]students belong to exactly one of the two clubs.
Neither of Two Properties
If the universe \(U\) contains \(N\) outcomes, then the number satisfying neither \(A\) nor \(B\) is the complement of \(A\cup B\):
\[ \boxed{N-|A\cup B|}. \]Using inclusion–exclusion,
\[ \boxed{N-|A|-|B|+|A\cap B|}. \]Example: Neither Language
A group contains \(40\) students. Of these, \(18\) study French, \(14\) study Spanish, and \(6\) study both.
First count those studying at least one language:
\[ 18+14-6=26. \]Then subtract from the total:
\[ 40-26=14. \]Therefore,
\[ \boxed{14} \]students study neither language.
Three Overlapping Sets
With three sets, pairwise overlap correction is not enough.
For finite sets \(A\), \(B\), and \(C\),
\[ \boxed{ |A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C| }. \]Why the Triple Intersection Is Added Back
Consider an element that belongs to all three sets.
In
\[ |A|+|B|+|C|, \]it is counted three times.
Subtracting the three pairwise intersections removes it three times:
\[ 3-3=0. \]But it should be counted once in the union.
Therefore, the triple intersection is added back once:
\[ 3-3+1=1. \]The Add-Subtract Pattern
Inclusion–exclusion alternates signs:
- add individual set sizes;
- subtract pairwise intersections;
- add triple intersections;
- subtract four-way intersections;
- continue alternating.
The alternating corrections ensure that every element in the union is counted exactly once.
Example: Three Activities
Suppose:
- \(28\) students participate in music;
- \(22\) participate in art;
- \(18\) participate in theater;
- \(9\) participate in both music and art;
- \(7\) participate in both music and theater;
- \(6\) participate in both art and theater;
- \(3\) participate in all three.
Then
\[ |M\cup A\cup T| = 28+22+18-9-7-6+3. \]Therefore,
\[ \boxed{49} \]students participate in at least one activity.
Pairwise Intersections Include Triple Members
Unless stated otherwise, a quantity such as
\[ |A\cap B| \]includes elements that may also belong to \(C\).
This is exactly the interpretation used in the standard three-set inclusion–exclusion formula.
At Least One Property
Inclusion–exclusion often counts outcomes satisfying at least one of several properties.
For two properties,
\[ \#(\text{at least one}) = |A|+|B|-|A\cap B|. \]For three properties, use the full three-set formula.
Complement of a Union
Sometimes inclusion–exclusion is used inside complementary counting.
If \(U\) is the universe, then
\[ |(A\cup B)^c| = |U|-|A\cup B|. \]Therefore,
\[ \boxed{|(A\cup B)^c| = |U|-|A|-|B|+|A\cap B|}. \]Example: Avoiding Two Forbidden Conditions
Suppose \(100\) candidate codes are under consideration.
Let \(A\) be the \(24\) codes violating rule \(A\), and let \(B\) be the \(31\) codes violating rule \(B\).
Suppose \(9\) codes violate both.
Invalid codes:
\[ 24+31-9=46. \]Valid codes:
\[ 100-46=54. \]Therefore,
\[ \boxed{54} \]codes satisfy both rules.
Divisibility by Several Numbers
Inclusion–exclusion is especially useful for divisibility problems.
Intersections are counted using common multiples.
For example,
\[ \{\text{multiples of }4\}\cap\{\text{multiples of }6\} \]is the set of multiples of
\[ \operatorname{lcm}(4,6)=12. \]Example: Multiples of 2, 3, or 5
Count integers from \(1\) through \(60\) divisible by \(2\), \(3\), or \(5\).
Individual counts:
\[ 30,\qquad20,\qquad12. \]Pairwise intersections:
\[ \left\lfloor\frac{60}{6}\right\rfloor=10, \] \[ \left\lfloor\frac{60}{10}\right\rfloor=6, \] \[ \left\lfloor\frac{60}{15}\right\rfloor=4. \]Triple intersection:
\[ \left\lfloor\frac{60}{30}\right\rfloor=2. \]Therefore,
\[ 30+20+12-10-6-4+2=44. \]Thus,
\[ \boxed{44} \]integers are divisible by at least one of \(2\), \(3\), or \(5\).
Counting Strings with Overlapping Properties
Inclusion–exclusion also applies to strings and codes.
Suppose we want strings that contain at least one \(A\) or at least one \(B\).
Let:
\[ X=\{\text{strings containing at least one }A\} \]and
\[ Y=\{\text{strings containing at least one }B\}. \]Then
\[ |X\cup Y|=|X|+|Y|-|X\cap Y|. \]Example: Strings Containing A or B
Four-character strings are formed from the symbols
\[ \{A,B,C,D\}, \]with repetition allowed.
Count strings containing at least one \(A\) or at least one \(B\).
A simpler complementary view is to exclude strings containing neither \(A\) nor \(B\).
Total strings:
\[ 4^4. \]Strings using only \(C\) and \(D\):
\[ 2^4. \]Therefore,
\[ \boxed{4^4-2^4=240}. \]This example shows that inclusion–exclusion and complementary counting can solve the same problem from different directions.
Choosing Between Inclusion–Exclusion and a Complement
If several desired properties overlap, inclusion–exclusion may be natural.
If the complement collapses the problem into one simple restriction, counting the complement may be shorter.
Both methods are valid when applied correctly.
Example: Neither of Three Properties
Suppose a universe contains \(120\) outcomes, and
\[ |A\cup B\cup C|=83. \]Then the number satisfying none of the three properties is
\[ 120-83=37. \]Therefore,
\[ \boxed{37}. \]Exactly Two of Three Properties
Suppose we know the pairwise intersections and the triple intersection.
The sum
\[ |A\cap B|+|A\cap C|+|B\cap C| \]counts an element in all three sets three times.
For “exactly two,” elements in all three should be counted zero times.
Therefore,
\[ \boxed{ \#(\text{exactly two}) = |A\cap B|+|A\cap C|+|B\cap C| -3|A\cap B\cap C| }. \]Example: Exactly Two Clubs
Suppose
\[ |A\cap B|=12,\qquad |A\cap C|=9,\qquad |B\cap C|=11, \]and
\[ |A\cap B\cap C|=4. \]Then the number belonging to exactly two clubs is
\[ 12+9+11-3(4)=20. \]Therefore,
\[ \boxed{20}. \]Exactly One of Three Properties
A useful way to find the number satisfying exactly one property is to subtract the elements that lie in multiple sets from the individual set totals.
One compact formula is
\[ \boxed{ |A|+|B|+|C| -2\bigl(|A\cap B|+|A\cap C|+|B\cap C|\bigr) +3|A\cap B\cap C| }. \]This formula is less frequently memorized than the union formula, so careful region reasoning is often preferable.
Venn Diagrams as Bookkeeping Tools
Venn diagrams can help organize inclusion–exclusion problems.
For three sets, it is often useful to fill the central triple intersection first, then determine the pairwise-only regions, then the single-set-only regions.
The diagram is not the principle itself; it is a bookkeeping aid for the same set relationships.
General Inclusion–Exclusion
For finite sets
\[ A_1,A_2,\ldots,A_n, \]the size of the union is obtained by alternating sums of intersections:
\[ \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. \]The final sign depends on the number of sets.
Why the General Pattern Works
Consider an outcome belonging to exactly \(r\) of the sets.
Inclusion–exclusion counts it with coefficient
\[ \binom{r}{1} -\binom{r}{2} +\binom{r}{3} -\cdots +(-1)^{r+1}\binom{r}{r}. \]This alternating sum equals
\[ 1. \]Thus every element in the union is ultimately counted exactly once.
Inclusion–Exclusion Is Corrective Counting
The method can be understood as repeated correction:
- count broadly;
- identify overcounted overlap;
- subtract that overlap;
- restore any outcomes removed too many times;
- continue until every outcome has coefficient \(1\).
Common Error: Adding Overlapping Sets Directly
If \(A\cap B\neq\varnothing\), then
\[ |A\cup B|\neq|A|+|B|. \]The overlap must be corrected:
\[ \boxed{|A\cup B|=|A|+|B|-|A\cap B|}. \]Common Error: Subtracting the Overlap Twice
In a two-set union, the overlap was counted twice initially.
We want it counted once.
Therefore, subtract it only once.
Common Error: Forgetting the Triple Intersection
For three sets, subtracting all three pairwise intersections removes elements in all three sets too many times.
The triple intersection must be added back:
\[ +|A\cap B\cap C|. \]Common Error: Treating Pairwise-Only Counts as Full Intersections
The standard formula assumes quantities such as
\[ |A\cap B| \]include elements that may also be in a third set.
If a problem instead gives the number in \(A\cap B\) but not \(C\), that is a different quantity and must be handled accordingly.
Common Error: Mixing Universes
When inclusion–exclusion is combined with complementary counting, all set counts must refer to the same universe.
A mismatch between the total universe and the sets being subtracted produces an invalid result.
A Reliable Procedure for Two Sets
- Define the sets \(A\) and \(B\).
- Find \(|A|\).
- Find \(|B|\).
- Find \(|A\cap B|\).
- Compute \(|A|+|B|-|A\cap B|\).
- Interpret the result in the original context.
A Reliable Procedure for Three Sets
- Define \(A\), \(B\), and \(C\).
- Add the three individual set sizes.
- Subtract all three pairwise intersections.
- Add the triple intersection.
- If needed, subtract the union from the universe to count none.
- Check that all intersection counts use consistent definitions.
Example: Full Three-Set Workflow
Among \(100\) students:
- \(45\) take algebra;
- \(38\) take geometry;
- \(31\) take statistics;
- \(16\) take algebra and geometry;
- \(13\) take algebra and statistics;
- \(11\) take geometry and statistics;
- \(5\) take all three.
The number taking at least one course is
\[ 45+38+31-16-13-11+5. \]Thus,
\[ \boxed{79} \]students take at least one of the three courses.
Therefore, the number taking none is
\[ 100-79=21. \]So,
\[ \boxed{21} \]students take none of the three courses.
Practice 1: Two Sets
A group contains \(24\) students in club \(A\), \(19\) in club \(B\), and \(7\) in both. How many students are in at least one of the two clubs?
Practice 2: Divisibility
How many integers from \(1\) through \(50\) are divisible by \(2\) or \(5\)?
Practice 3: Exactly One
Suppose \(|A|=30\), \(|B|=22\), and \(|A\cap B|=9\). How many elements belong to exactly one of the two sets?
Practice 4: Neither
A universe contains \(80\) elements. If \(|A|=35\), \(|B|=28\), and \(|A\cap B|=12\), how many elements belong to neither set?
Practice 5: Three Sets
Suppose
\[ |A|=20,\quad |B|=18,\quad |C|=15, \] \[ |A\cap B|=6,\quad |A\cap C|=5,\quad |B\cap C|=4, \]and
\[ |A\cap B\cap C|=2. \]Find \(|A\cup B\cup C|\).
Practice 6: Multiples of 3 or 4
How many integers from \(1\) through \(100\) are divisible by \(3\) or \(4\)?
Practice 7: At Least One Activity
In a group, \(32\) people participate in activity \(A\), \(27\) in activity \(B\), and \(10\) in both. How many participate in at least one?
Practice 8: Exactly Two of Three
Suppose
\[ |A\cap B|=10,\quad |A\cap C|=8,\quad |B\cap C|=7, \]and
\[ |A\cap B\cap C|=3. \]How many elements belong to exactly two of the three sets?
Practice 9: None of Three
A universe has \(90\) elements. Suppose the union of three properties contains \(68\) elements. How many elements satisfy none of the three properties?
Practice 10: Identify the Error
A student computes
\[ |A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| \]and stops. What term may be missing, and why?
Practice Answers
Practice 1
\[ \boxed{24+19-7=36}. \]Practice 2
Multiples of \(2\):
\[ 25. \]Multiples of \(5\):
\[ 10. \]Multiples of both are multiples of \(10\):
\[ 5. \]Therefore,
\[ \boxed{25+10-5=30}. \]Practice 3
\[ \boxed{30+22-2(9)=34}. \]Practice 4
First find the union:
\[ 35+28-12=51. \]Then subtract from the universe:
\[ \boxed{80-51=29}. \]Practice 5
\[ \boxed{20+18+15-6-5-4+2=40}. \]Practice 6
Multiples of \(3\):
\[ \left\lfloor\frac{100}{3}\right\rfloor=33. \]Multiples of \(4\):
\[ \left\lfloor\frac{100}{4}\right\rfloor=25. \]Multiples of both are multiples of \(12\):
\[ \left\lfloor\frac{100}{12}\right\rfloor=8. \]Therefore,
\[ \boxed{33+25-8=50}. \]Practice 7
\[ \boxed{32+27-10=49}. \]Practice 8
\[ 10+8+7-3(3)=16. \]Therefore,
\[ \boxed{16} \]elements belong to exactly two sets.
Practice 9
\[ \boxed{90-68=22}. \]Practice 10
The missing term is
\[ +|A\cap B\cap C|. \]Elements in all three sets are counted three times initially and then removed three times by the pairwise subtractions, leaving them counted zero times. Adding the triple intersection restores each one once.
What to Remember
For two finite sets,
\[ \boxed{|A\cup B|=|A|+|B|-|A\cap B|}. \]For three finite sets,
\[ \boxed{ |A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C| }. \]- Add broad set totals.
- Subtract overlaps counted too many times.
- Add back higher-order overlaps removed too many times.
- Use complements to count “none” or “valid” outcomes when convenient.
- Keep intersection definitions consistent.
- Remember that the goal is to count every outcome exactly once.
Where We Go Next
Inclusion–exclusion corrects overlap between sets. Another foundational counting idea proves that repetition or collision must occur whenever more objects are placed into fewer available categories.
The next lesson, The Pigeonhole Principle, develops this inevitability as a powerful counting and existence argument.