,

Contents · Inclusion–exclusion principle

Overview

Summary

The inclusion–exclusion principle counts the size of unions by alternately adding and subtracting overlaps. It generalizes to probability and to counting surjections/derangements.

Details

Concepts
  • Two sets: |A ∪ B| = |A| + |B| − |A ∩ B|.
  • Three sets: add singles, subtract pairwise, add triple: |A ∪ B ∪ C| = Σ|A_i| − Σ|A_i∩A_j| + |A∩B∩C|.
  • General n sets: |⋃ A_i| = Σ|A_i| − Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| − ... + (−1)^{n+1}|A_1∩⋯∩A_n|.
  • Probability version replaces cardinalities with probabilities.
  • Applications: derangements D_n ≈ n!/e; counting surjections via Stirling numbers of the second kind: m!·S(n,m).

Exercises

Hands-on
  1. Compute |A ∪ B ∪ C| given |A|,|B|,|C| and pairwise/triple intersections.
  2. Use inclusion–exclusion to count permutations of n with no fixed points (D_n).
  3. Count the number of onto functions from an n-element set to an m-element set.

©