Inclusion–Exclusion

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

To count a union of overlapping sets, add the sizes, subtract the pairwise overlaps, add back the triples, and alternate. Inclusion–exclusion corrects for the double-counting at every level. Its most famous output is the derangement: permutations that fix nothing.

Alternating correction

Singletons overcount the overlaps, so you subtract pairwise intersections; but now the triple is subtracted too many times, so you add it back. The signs alternate by the size of the intersecting group.

Derangements

How many permutations of n items leave nothing in place? Apply inclusion–exclusion over the "item i is fixed" events: D(n) = n!·(1 − 1/1! + 1/2! − … ± 1/n!). The ratio D(n)/n! converges to 1/e fast.

Scheme

(define (factorial n)
  (if (<= n 1) 1 (* n (factorial (- n 1)))))

; D(n) = sum_{k=0}^n (-1)^k * n!/k!   (inclusion-exclusion)
(define (derangements n)
  (let loop ((k 0) (acc 0))
    (if (> k n) acc
        (loop (+ k 1)
              (+ acc (* (expt -1 k)
                        (/ (factorial n) (factorial k))))))))

(display "D(1) = ") (display (derangements 1)) (newline)  ; 0
(display "D(2) = ") (display (derangements 2)) (newline)  ; 1
(display "D(3) = ") (display (derangements 3)) (newline)  ; 2
(display "D(4) = ") (display (derangements 4)) (newline)  ; 9
(display "D(5) = ") (display (derangements 5)) (newline)  ; 44

Neighbors

🎲 Probability — inclusion–exclusion is the union bound made exact
🧮 Ch.5 Generating Functions — derangements have a clean exponential generating function

← Bijective Proof · 3 of 10 by june.kim Generating Functions · 5 of 10 →