$$ 1_{\bigcap_{i\in[n]} {A_i}^C} = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert} 1_{\bigcap_{i\in S} {A_i}} $$
数え上げ測度で積分したら集合の要素数の包除原理になるし、確率測度で積分したら確率の包除原理になる。
集合の濃度に関する包除原理 $\left\lvert \bigcap_{i\in [n]} {A_i}^C\right\rvert = \sum_{S\subseteq [n]} (-1)^{\lvert S \rvert } \left\lvert \bigcap_{i \in S} A_i\right\rvert$ について考える。
$N$ 個の制約があって、$N$ 個の制約をすべて満たす要素全体の集合の要素数を求めたいという問題を考える。$A_i$ を $i$ 番目の制約に違反している要素全体の集合とすると、$N$ 個の制約をすべて満たす要素全体の集合は $\bigcap_{i\in [N]} {A_i}^C$ である。
$\sum_{S\subseteq [n]} (-1)^{\lvert S \rvert } \left\lvert \bigcap_{i \in S} A_i\right\rvert$ の $S$ は違反している制約の集合だと言える。
$\bigcap_{i \in S} A_i$ が扱いやすい場合に包除原理は有効である。
以下は例
| 問題 | $A_i$ の定義 (i番目の制約違反の集合) | $\left\lvert \bigcap_{i \in S} A_i\right\rvert$ |
|---|---|---|
| 長さ $n$ の撹乱順列の数 | $p_i = i$ を満たす順列 $p$ 全体 | $(n - \lvert S\rvert)!$ |
| $[n]\to [m]$ の全射の数 | $i \in \operatorname{Im}f$ を満たす写像 $f$ 全体 | $(m- \lvert S \rvert )^n$ |
| $n$ 未満で$n$と互いに素な自然数の数 | ||
| ただし、$n = \prod_{k=1}^d {p_k}^{e_k}$ と素因数分解できるとする。 | $n$ 未満の自然数で $p_i$ の倍数であるもの全体 | $n/\prod_{i\in S} p_i$ |