Discrete Math › Section D · Counting › Topic D.3

Overlaps and inclusion-exclusion

The sum principle only works when cases do not overlap. Real questions overlap all the time, and the principle of inclusion-exclusion is the bookkeeping that counts every outcome exactly once.

When cases overlap

How many whole numbers from 1 to 60 are multiples of 4 or multiples of 6? There are 15 multiples of 4 and 10 multiples of 6, but the answer is not 25. Numbers such as 12, 24 and 36 are multiples of both, so they sit in both lists and adding the lists counts them twice. The sum principle from "The sum and product principles" required disjoint sets, and these sets are not disjoint. The fix: add the sets, then subtract what was double-counted. Making that precise for any number of sets is the principle of inclusion-exclusion, or PIE.

Pictures first: Venn diagrams

A Venn diagram draws each set as a circle inside a rectangle that stands for the universe. Two circles split the picture into four regions: in \(A\) only, in \(B\) only, in both, and in neither. Three circles make eight regions. The most reliable way to fill a diagram is from the inside out. Put the count for the overlap of all the sets in the centre first, then work outwards, subtracting what has already been placed from each larger count. Every outcome lands in exactly one region, so adding the regions counts each outcome exactly once. The formulas below are this picture written as algebra.

Inclusion-exclusion for two sets

For any finite sets \(A\) and \(B\),

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

An element in only one set is counted once by \(|A| + |B|\). An element in both is counted twice, and the subtraction removes one copy. For the multiples question, let \(A\) be the multiples of 4 and \(B\) the multiples of 6 in 1 to 60. A number is in both exactly when it is a multiple of 12, their least common multiple, so \(|A \cap B| = 5\). Then \(|A \cup B| = 15 + 10 - 5 = 20\). When \(A\) and \(B\) are disjoint, the overlap is 0 and the sum principle returns.

Worked example: bit strings with two conditions

How many 8-bit strings start with 1 or end with 00? 1. Let \(A\) be the strings starting with 1. The other 7 bits are free, so \(|A| = 2^7 = 128\). 2. Let \(B\) be the strings ending in 00. The first 6 bits are free, so \(|B| = 2^6 = 64\). 3. Strings in both start with 1 and end in 00, leaving 5 free bits: \(|A \cap B| = 2^5 = 32\). 4. By inclusion-exclusion, \(|A \cup B| = 128 + 64 - 32 = 160\). 5. Check with the complement: strings in neither set start with 0 and do not end in 00, giving \(1 \cdot 2^5 \cdot 3 = 96\), and \(256 - 96 = 160\).

Inclusion-exclusion for three sets

For three finite sets, add the singles, subtract the pairs, and add back the triple:

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

Why the final term? An element in all three sets is added three times by the single terms and subtracted three times by the pair terms, leaving it uncounted, so it must be added once more. An element in exactly two sets is added twice and subtracted once: net 1. An element in exactly one set is added once and never subtracted. Every element of the union is counted exactly once.

Worked example: multiples of 3, 5 or 7

How many numbers from 1 to 300 are multiples of 3, 5 or 7? 1. Singles: \(|A| = 300/3 = 100\), \(|B| = 300/5 = 60\), and \(|C| = 42\), since \(7 \cdot 42 = 294\). 2. Pairs: multiples of 15, 21 and 35, giving 20, 14 and 8 (because \(21 \cdot 14 = 294\) and \(35 \cdot 8 = 280\)). 3. Triple: multiples of 105, namely 105 and 210, so 2. 4. Combine:

100 + 60 + 42 - 20 - 14 - 8 + 2 = 162

5. So \(300 - 162 = 138\) numbers are divisible by none of 3, 5 or 7. A direct computer count agrees with both figures.

Worked example: filling a three-circle diagram

In a group of 50 students, 22 play football, 18 basketball and 15 tennis; 7 play football and basketball, 5 football and tennis, 4 basketball and tennis, and 2 play all three. 1. Centre: 2. 2. Exactly two sports: \(7 - 2 = 5\), \(5 - 2 = 3\) and \(4 - 2 = 2\). 3. Exactly one: football only \(22 - 5 - 3 - 2 = 12\), basketball only \(18 - 5 - 2 - 2 = 9\), tennis only \(15 - 3 - 2 - 2 = 8\). 4. The union is \(12 + 9 + 8 + 5 + 3 + 2 + 2 = 41\). 5. The formula agrees: \(55 - 16 + 2 = 41\). So 9 students play none of the three.

The general pattern

The same alternating pattern works for any number of sets. Add the sizes of the single sets, subtract the sizes of all pairwise intersections, add all triple intersections, subtract all quadruple intersections, and continue until the intersection of every set. For \(n\) sets there are \(\binom{n}{j}\) intersections of \(j\) sets at each stage, so four sets need \(4 + 6 + 4 + 1 = 15\) terms. The full version drives "Advanced counting: derangements and functions", where intersections are easy to count but the union is not.

Overlaps hidden inside a product

Overlaps can also spoil the product principle. Ask how many ways 10 people can form a pair to share a desk. Choosing a first person in 10 ways and a second in 9 ways gives 90, but every pair has been counted twice: Ana then Ben and Ben then Ana are the same pair. The correct count is \(90 / 2 = 45\). The product principle counts sequences, where order matters. When the outcomes are unordered, each one appears several times among the sequences, and the count must be corrected, here by dividing. "Combinations and permutations" turns this repair into a general rule.

Common mistakes to avoid

First, adding overlapping sets with no correction, which double-counts the overlap. Second, stopping the three-set formula after subtracting the pairs: the triple intersection must be added back. Third, using the product of two divisors instead of their least common multiple: multiples of both 4 and 6 are multiples of 12, not of 24. Fourth, filling a Venn diagram from the outside in, which puts elements in several regions at once; start from the centre. Fifth, confusing "in at least one set" (the union) with "in exactly one set", which also excludes everything in the overlaps.

Key takeaways

For overlapping sets, add the sizes and subtract what was double-counted: \(|A \cup B| = |A| + |B| - |A \cap B|\). For three sets, add singles, subtract pairs and add back the triple, so every element of the union counts exactly once. The pattern alternates for any number of sets. Venn diagrams filled from the centre outwards make every region visible. Complements give the count in none of the sets. Counting unordered outcomes by ordered stages hides an overlap that must be divided out.

Flashcards

Flashcard

PIE

The principle of inclusion-exclusion

Counts a union when the sets overlap.

Test your understanding

Question 1 of 5

How many numbers from 1 to 100 are multiples of 4 or multiples of 10?

Question 2 of 5

Sets have |A| = 20, |B| = 15, |C| = 10, |A ∩ B| = 6, |A ∩ C| = 4, |B ∩ C| = 3 and |A ∩ B ∩ C| = 2. What is |A ∪ B ∪ C|?

Question 3 of 5

In a class of 40, 25 students like maths, 18 like music and 10 like both. How many like neither?

Question 4 of 5

How many 6-bit strings start with 1 or end with 1?

Question 5 of 5

Why does the three-set formula end by adding |A ∩ B ∩ C|?

← Previous topicNext topic →