Sign in to watch this lesson
Advanced - Combinatorics, Games and Puzzles · 4:38
Inclusion-Exclusion
Inclusion-exclusion counts too much on purpose and then corrects with alternating signs. We count six capped numbers that sum to twenty by subtracting the solutions that break a cap and adding back the ones removed twice, see on a three-set Venn diagram why every element ends up counted exactly once, turn the rule into a bitmask loop whose sign is the parity of the popcount, and derive the derangement formula behind the hat-check puzzle and its limit 1/e.
You will learn
- Apply |A1 ∪ ... ∪ An| = Σ over nonempty J of (-1)^(|J|-1) |∩_{j∈J} Aj| and explain why every element is counted exactly once
- Count solutions of x1 + ... + xd = s with 0 <= xi <= b in O(d) as Σ (-1)^i C(d, i) C(s - (b+1) i + d - 1, d - 1), treating negative upper indices as 0
- Implement inclusion-exclusion as a bitmask loop with sign from popcount parity, using lcm and stopping early to avoid overflow
- Derive D_n = n! Σ (-1)^i / i! and explain why the chance of no fixed point tends to 1/e