Lesson 2 of 8 · 17 min
Inclusion–exclusion for overlapping sets
Count the elements in a union of two or three sets without double counting, using Venn diagrams and the inclusion–exclusion formulas.
What you will be able to do
- Explain why over-counts when and overlap.
- Use to count a union of two sets.
- Use the three-set inclusion–exclusion formula and a Venn diagram to count unions and regions.
- Count "neither", "only" and "exactly one" groups from a Venn diagram or the complement.
Your class has 28 students. 16 play a sport and 12 learn an instrument. Does everyone do at least one of the two? suggests so. But if some students do both, they have been counted twice, once in each group.
Definition
Set notation
- is the number of elements in set (some books write ).
- , the union: everything in or or both.
- , the intersection: everything in both and .
- , the complement: everything that is not in .
- , the universal set: everything being counted.
Tap regions to shade them. and , but the 5 students in the overlap belong to both sets.
Adding counts the 5 students in the overlap twice, once in each set. Subtract them once and every student is counted exactly once: students do at least one, and do neither.
Key idea
Inclusion–exclusion for two sets
Include both sets, then exclude the part you counted twice. If and do not overlap, and this is just the addition principle.
Sets and have , and . Find .
Worked example
A survey of sport and music
In a survey of 40 Year 11 students, 22 play a sport, 15 play a musical instrument and 8 do both.
(a) How many students play a sport or an instrument?
(b) How many do neither?
(c) How many play a sport but not an instrument?
Step 1: Name the sets
Let be the students who play a sport and those who play an instrument. Then , and .
Step 2: Use inclusion–exclusion
The 8 students who do both are in and in , so counts them twice.
Step 3: Use the complement for "neither"
students do neither.
Step 4: Remove the overlap from S
Sport but not an instrument: .
The 22 who play a sport include the 8 who also play an instrument.
Try it yourself first, then check the working one step at a time.
Answer
(a) 29 students (b) 11 students (c) 14 students
Method
Name the sets and write down the given counts.
Union: add the sets, subtract the overlap.
Neither: the total minus the union.
" but not ": .
Watch out for
Answering (a) with , which counts the 8 students twice.
Answering (c) with 22: "plays a sport" includes those who also play an instrument.
Three sets. With three circles there are seven regions inside them. Add and some regions are counted more than once, as the diagram shows. Subtracting the three pair overlaps fixes the regions in exactly two sets, but the centre was counted three times and is then subtracted three times. So it has to be added back.
How many times counts each region. Subtracting the three pair overlaps turns each 2 into 1, but turns the centre into 0, so is added back.
Key idea
Inclusion–exclusion for three sets
Add the singles, subtract the pairs, add back the triple. Both inclusion–exclusion formulas are in the QCAA formula book.
Check the formula region by region. Sport has 18 students, Music 14 and Drama 12; the pair overlaps hold 6, 5 and 4; and 2 do all three. , the same as adding the seven regions inside the circles.
Sets , and have , , , , , and . Find .
Common mistake
A pair overlap includes the centre
In the formula, means everything in both and , including anything also in . If a question says "4 people do only sport and music", that is the region , and you add the centre to it to get . Read "only" carefully.
Filling a three-set Venn diagram
Start in the centre
Write in the middle region.
Fill the "exactly two" regions
Subtract the centre from each pair overlap, for example .
Fill the "only" regions
Subtract everything already written inside a circle from that set's total.
Fill the outside
Subtract the union from the size of the universal set to get "none".
Worked example
Integers divisible by 2, 3 or 5
How many integers from 1 to 1000 inclusive are divisible by 2, 3 or 5? Hence find how many are divisible by none of 2, 3 and 5.
Step 1: Define the sets
Let , and be the integers from 1 to 1000 that are divisible by 2, 3 and 5 respectively. We want .
Step 2: Count each set
The number of multiples of up to 1000 is the whole-number part of , so , and .
The multiples of 3 are , so there are 333 of them. Do not round up.
Step 3: Count the pair overlaps
Divisible by 2 and 3 means divisible by 6, and so on: (multiples of 6), (multiples of 10) and (multiples of 15).
2, 3 and 5 are prime, so a number divisible by two of them is divisible by their product.
Step 4: Count the triple overlap
, the multiples of 30 (since ).
Step 5: Apply inclusion–exclusion
Step 6: Take the complement
integers are divisible by none of 2, 3 and 5.
Try it yourself first, then check the working one step at a time.
Answer
734 integers from 1 to 1000 are divisible by 2, 3 or 5, and 266 are divisible by none of them.
Method
Define one set for each condition.
Count each set and each intersection (an intersection of "divisible by" sets is "divisible by the lowest common multiple").
Add the singles, subtract the pairs, add back the triple.
"None" is the total minus the union.
Watch out for
Rounding up to 334: there are only 333 multiples of 3 up to 1000.
Forgetting to add back , which gives 701.
For divisors that share a factor, such as 4 and 6, the overlap is the multiples of the lowest common multiple (12), not of the product (24).
In a survey of 60 households, 38 have a dog, 27 have a cat and 14 have both. How many households have neither a dog nor a cat?
Worked example
How many passwords follow the rules?
A website's passwords are exactly 8 characters long. Each character is one of the 26 lowercase letters or one of the 10 digits, and characters may repeat.
(a) How many passwords are possible with no other rules?
(b) The website now requires at least one digit. How many passwords follow this rule?
(c) It then also requires at least one letter. Use inclusion–exclusion to find how many passwords follow both rules.
(d) An attacker's computer can test passwords per second. How long would it take to test every password allowed in (c)? Comment on what the rules do to security.
Step 1: Count all passwords
Each of the 8 slots has 36 options: .
Step 2: Use the complement for "at least one digit"
Passwords with no digit use letters only, and there are of them. So the number with at least one digit is .
Every password either contains a digit or does not, so (with a digit) = (all) − (no digit).
Step 3: Name the passwords that break a rule
Let be the passwords with no digit, so , and the passwords with no letter, so . A password breaks a rule if it is in .
Step 4: Use inclusion–exclusion
A password in would have no digits and no letters, which is impossible, so and .
Inclusion–exclusion still works when the overlap is empty. It then reduces to the addition principle.
Step 5: Subtract from the total
passwords follow both rules.
Step 6: Find the time
seconds, which is about 4.4 minutes.
Step 7: Evaluate the rules
Each rule removes passwords: together they cut the number of possibilities by about 7.4%, so an attacker testing every password finishes slightly sooner, not later. Rules like these help only by stopping people from choosing common words. Length matters far more: two extra characters multiply the number of passwords by .
Try it yourself first, then check the working one step at a time.
Answer
(a) (b) (c) (d) about 261 seconds, or 4.4 minutes. The rules slightly reduce the number of possible passwords; extra length is what makes them much harder to break.
Method
Count everything first.
"At least one" means subtract the outcomes with none.
Two rules means inclusion–exclusion on the outcomes that break them.
Interpret the size of the answer in the context.
Watch out for
Counting "at least one digit" as : that counts passwords with several digits more than once.
Subtracting and and then also subtracting an overlap that does not exist.
Exam tip
Draw the diagram
When a question gives counts in words, sketch a Venn diagram and fill it from the centre outwards. It checks your formula and makes "exactly one", "only" and "neither" quick to read off. Remember that means "in at least one of and ".
Summary
: include both sets, then exclude the overlap you counted twice.
For three sets, add the singles, subtract the three pair overlaps, then add back .
"Neither" or "none" is the complement: the total minus the union.
A pair overlap such as includes the centre region; "only and " does not.
Fill a Venn diagram from the centre outwards, then read off any region.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.