包除原理
この原理は時に以下のような形で表される。有限集合 S のべき集合 2 上で定義された関数 f, g が
g ( A ) = ∑ B ⊆ A f ( B ) {\displaystyle g(A)=\sum _{B\subseteq A}f(B)}
を満たすならば、
f ( A ) = ∑ B ⊆ A ( − 1 ) | A ∖ B | g ( B ) . {\displaystyle f(A)=\sum _{B\subseteq A}(-1)^{\left|A\setminus B\right|}g(B).}
この形は半順序集合 2 の隣接代数におけるメビウスの反転公式となる。
また、包除原理は確率においても以下のように用いられる。
Pr ( ⋃ i A i ) = ∑ i Pr ( A i ) − ∑ i < j Pr ( A i ∩ A j ) + ⋯ + ( − 1 ) n − 1 Pr ( ⋂ i A i ) {\displaystyle \Pr \left(\bigcup _{i}A_{i}\right)=\sum _{i}\Pr \left(A_{i}\right)-\sum _{i<j}\Pr \left(A_{i}\cap A_{j}\right)+\cdots +(-1)^{n-1}\Pr \left(\bigcap _{i}A_{i}\right)}
ボンフェローニの不等式によれば、この公式の始めの k 項の和は左辺の上界と下界を交互にとる: