Inclusion-Exclusion Principle: Counting the Union of Sets

Learn the Inclusion-Exclusion Principle, a counting technique for determining the size of the union of sets, especially when sets overlap. This guide provides the formula for two and three sets, along with illustrative examples.



The Inclusion-Exclusion Principle

Understanding the Principle

The Inclusion-Exclusion Principle is a counting technique used to find the size of the union of sets. It's particularly useful when dealing with overlapping sets (sets that share some elements). For two finite sets A and B, the principle states:

n(A ∪ B) = n(A) + n(B) - n(A ∩ B)

In words: To find the number of elements in A or B (or both), we add the number of elements in A and the number of elements in B, then subtract the number of elements that are in both A and B (to avoid double-counting).

Extending the Principle to Three Sets

The principle can be extended to three or more sets. For three sets A, B, and C:

n(A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C)

Example: Newspaper Subscriptions

Let's say a town has 10,000 families. We have the following subscription data for three newspapers (A, B, and C):

  • n(A) = 4000 (40% subscribe to A)
  • n(B) = 2000 (20% subscribe to B)
  • n(C) = 1000 (10% subscribe to C)
  • n(A ∩ B) = 500 (5% subscribe to both A and B)
  • n(B ∩ C) = 300 (3% subscribe to both B and C)
  • n(A ∩ C) = 400 (4% subscribe to both A and C)
  • n(A ∩ B ∩ C) = 200 (2% subscribe to all three)

We can use the inclusion-exclusion principle to answer various questions:

Calculating Subscription Combinations

  1. Families subscribing to all three newspapers: This is given as n(A ∩ B ∩ C) = 200.
  2. Families subscribing to at least one newspaper: n(A ∪ B ∪ C) = 4000 + 2000 + 1000 - 500 - 400 - 300 + 200 = 6000 (60%).
  3. Families subscribing to newspaper A only: 4000 - (500 + 400 - 200) = 3300 (33%).
  4. Families subscribing to newspaper B only: 2000 - (500 + 300 - 200) = 1400 (14%).
  5. Families subscribing to newspaper C only: 1000 - (400 + 300 - 200) = 500 (5%).
  6. Families subscribing to none of the newspapers: 10000 - 6000 = 4000 (40%).
  7. Families subscribing to exactly one newspaper: 3300 + 1400 + 500 = 5200 (52%).
  8. Families subscribing to exactly two newspapers: (500 - 200) + (300 - 200) + (400 - 200) = 600 (6%).
  9. Families subscribing to at least two newspapers: 600 + 200 = 800 (8%).
  10. Families subscribing to at most two newspapers: 10000 - 200 = 9800 (98%).

Conclusion

The Inclusion-Exclusion Principle is a fundamental counting method that helps us accurately determine the size of unions of sets, especially when dealing with overlaps. It finds applications in probability, combinatorics, and various other areas.