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 ∣A∣+∣B∣|A| + |B| over-counts when AA and BB overlap.
  • Use ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B| 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? 16+12=2816 + 12 = 28 suggests so. But if some students do both, they have been counted twice, once in each group.

Definition

Set notation

  • ∣A∣|A| is the number of elements in set AA (some books write n(A)n(A)).
  • A∪BA \cup B, the union: everything in AA or BB or both.
  • A∩BA \cap B, the intersection: everything in both AA and BB.
  • A′A', the complement: everything that is not in AA.
  • ξ\xi, the universal set: everything being counted.
Interactive

Sport and music

Tap regions to shade them. ∣Sport∣=11+5=16|\text{Sport}| = 11 + 5 = 16 and ∣Music∣=7+5=12|\text{Music}| = 7 + 5 = 12, but the 5 students in the overlap belong to both sets.

Adding 16+1216 + 12 counts the 5 students in the overlap twice, once in each set. Subtract them once and every student is counted exactly once: 16+12−5=2316 + 12 - 5 = 23 students do at least one, and 28−23=528 - 23 = 5 do neither.

Key idea

Inclusion–exclusion for two sets

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|

Include both sets, then exclude the part you counted twice. If AA and BB do not overlap, ∣A∩B∣=0|A \cap B| = 0 and this is just the addition principle.

Sets AA and BB have ∣A∣=30|A| = 30, ∣B∣=24|B| = 24 and ∣A∩B∣=9|A \cap B| = 9. Find ∣A∪B∣|A \cup B|.

Worked example

A survey of sport and music

  • Simple familiar
  • Technology free

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?

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Name the sets and write down the given counts.

  2. Union: add the sets, subtract the overlap.

  3. Neither: the total minus the union.

  4. "AA but not BB": ∣A∣−∣A∩B∣|A| - |A \cap B|.

Watch out for

  • Answering (a) with 22+15=3722 + 15 = 37, 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 ∣A∣+∣B∣+∣C∣|A| + |B| + |C| 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 ∣A∣+∣B∣+∣C∣|A| + |B| + |C| counts each region. Subtracting the three pair overlaps turns each 2 into 1, but turns the centre into 0, so ∣A∩B∩C∣|A \cap B \cap C| is added back.

Key idea

Inclusion–exclusion for three sets

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

Add the singles, subtract the pairs, add back the triple. Both inclusion–exclusion formulas are in the QCAA formula book.

Interactive

Three activities

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. 18+14+12−6−5−4+2=3118 + 14 + 12 - 6 - 5 - 4 + 2 = 31, the same as adding the seven regions inside the circles.

Sets AA, BB and CC have ∣A∣=25|A| = 25, ∣B∣=20|B| = 20, ∣C∣=16|C| = 16, ∣A∩B∣=8|A \cap B| = 8, ∣A∩C∣=6|A \cap C| = 6, ∣B∩C∣=5|B \cap C| = 5 and ∣A∩B∩C∣=3|A \cap B \cap C| = 3. Find ∣A∪B∪C∣|A \cup B \cup C|.

Common mistake

A pair overlap includes the centre

In the formula, ∣A∩B∣|A \cap B| means everything in both AA and BB, including anything also in CC. If a question says "4 people do only sport and music", that is the region A∩B∩C′A \cap B \cap C', and you add the centre to it to get ∣A∩B∣|A \cap B|. Read "only" carefully.

Filling a three-set Venn diagram

  1. Start in the centre

    Write ∣A∩B∩C∣|A \cap B \cap C| in the middle region.

  2. Fill the "exactly two" regions

    Subtract the centre from each pair overlap, for example ∣A∩B∣−∣A∩B∩C∣|A \cap B| - |A \cap B \cap C|.

  3. Fill the "only" regions

    Subtract everything already written inside a circle from that set's total.

  4. 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

  • Complex familiar
  • Technology free

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.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Define one set for each condition.

  2. Count each set and each intersection (an intersection of "divisible by" sets is "divisible by the lowest common multiple").

  3. Add the singles, subtract the pairs, add back the triple.

  4. "None" is the total minus the union.

Watch out for

  • Rounding 10003=333.3…\frac{1000}{3} = 333.3\ldots up to 334: there are only 333 multiples of 3 up to 1000.

  • Forgetting to add back ∣A∩B∩C∣|A \cap B \cap C|, 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?

  • Complex unfamiliar
  • Technology active

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 101010^{10} passwords per second. How long would it take to test every password allowed in (c)? Comment on what the rules do to security.

7 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Count everything first.

  2. "At least one" means subtract the outcomes with none.

  3. Two rules means inclusion–exclusion on the outcomes that break them.

  4. Interpret the size of the answer in the context.

Watch out for

  • Counting "at least one digit" as 10×36710 \times 36^7: that counts passwords with several digits more than once.

  • Subtracting 26826^8 and 10810^8 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 ∣A∪B∣|A \cup B| means "in at least one of AA and BB".

Summary

  • ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|: include both sets, then exclude the overlap you counted twice.

  • For three sets, add the singles, subtract the three pair overlaps, then add back ∣A∩B∩C∣|A \cap B \cap C|.

  • "Neither" or "none" is the complement: the total minus the union.

  • A pair overlap such as ∣A∩B∣|A \cap B| includes the centre region; "only AA and BB" 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.

Lesson 2 of 80% read

Save your progress with a free account