容斥原理計數

容斥原理 (inclusion–exclusion) 數「至少屬於一個集合」的元素:$$|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B\cap C|$$ 交替加減是為了讓每個元素恰好被數一次。「一個都不屬於」= 全體減去聯集。

算例:1 到 100 中被 2 或 3 整除:$50 + 33 - 16 = 67$(同時被整除看 $\text{lcm} = 6$);都不被整除 33 個。

經典應用是錯排 (derangement):$n$ 個人都拿不到自己帽子的方法數 $D_n = n!\sum_{k=0}^n\frac{(-1)^k}{k!}$,$D_3 = 2$、$D_4 = 9$、$D_5 = 44$;$n$ 大時 $D_n/n!\to\frac{1}{e}\approx0.37$。

容斥也用來數映成函數個數、歐拉函數 $\varphi(n)$ 的公式、以及機率裡「至少一個」的精確計算。