Sets and relations · Definition

Inclusion-exclusion principle

discrete mathematicscountingsets

Before you start you need to know

It solves the problem of counting «those with at least one property» when the properties overlap.

Definition

It counts the elements of the union of finite sets \(A\), \(B\), \(C\), … by adding their sizes and correcting what was counted too often in the intersections.

\[\begin{aligned}|A\cup B|&=|A|+|B|-|A\cap B|\\|A\cup B\cup C|&=|A|+|B|+|C|\\&\quad-|A\cap B|-|A\cap C|-|B\cap C|\\&\quad+|A\cap B\cap C|\end{aligned}\]

If \(|A|\) and \(|B|\) are added, the elements of \(A\cap B\) are counted twice; that is why \(|A\cap B|\) is subtracted once. With three sets, subtracting the three pairwise intersections removes too much from the elements lying in all three (counted three times, subtracted three times), so \(|A\cap B\cap C|\) must be added back.

In general, for \(n\) sets the terms alternate in sign: single sizes are added, pairwise intersections subtracted, triple intersections added, and so on. Each element of the union ends up counted exactly once, which can be checked with the binomial theorem.

A guiding example: the integers from 1 to 100 divisible by 2 or 3 number \(50+33-16=67\), because the 16 multiples of 6 were counted twice. Subtracting from 100 gives those divisible by neither: 33. This trick of counting the complement is very common.

Typical mistakes are forgetting the triple-intersection term or applying the principle to sets that are not finite. If the sets are disjoint, all intersections are empty and the sum rule is recovered.

Think about it

Why is \(|A\cap B\cap C|\) added at the end for three sets?

An element in all three sets is added three times and subtracted three times in the pairwise intersections; it is counted zero times and must be restored once.

What is \(|A\cup B|\) if \(A\) and \(B\) are disjoint?

It is \(|A|+|B|\), since \(|A\cap B|=0\); this is the sum rule.

Exercises 10

  1. If \(|A|=12\), \(|B|=9\) and \(|A\cap B|=4\), what is \(|A\cup B|\)?
  2. Of 30 students, 18 play soccer, 15 play basketball and 7 play both. How many play neither?
  3. How many integers from 1 to 100 are divisible by 2 or by 3?
  4. How many integers from 1 to 100 are divisible by 2, 3 or 5?
  5. How many integers from 1 to 100 are divisible by neither 2 nor 3?
  6. Suppose \(|A|=10\), \(|B|=8\), \(|C|=6\), \(|A\cap B|=3\), \(|A\cap C|=2\), \(|B\cap C|=1\) and \(|A\cap B\cap C|=1\). What is \(|A\cup B\cup C|\)?
  7. If \(|A\cup B|=|A|+|B|\), what follows?
  8. How many binary strings of length 8 start with 1 or end with 00?
  9. If \(|A\cup B|=20\), \(|A|=14\) and \(|B|=11\), what is \(|A\cap B|\)?
  10. How many integers from 1 to 1000 are divisible by none of 3, 5 and 7?

What comes next

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §8.5
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §9.3
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §8.1