包除原理

組合せ数学において、包除原理（ほうじょげんり、Inclusion-exclusion principle）とはA₁, ..., A_n を有限集合としたとき

$\left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,i < j}\left|A_i\cap A_j\right|$ $+\sum_{i,j,k\,:\,i<j<k}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\cdots\ \pm \left|A_1\cap\cdots\cap A_n\right|$

となることをいう。ここで |A| は集合 A の濃度をあらわす。例えば、n = 2 のときは、二重計算の特別な場合となる。簡単に言えば、集合 A と B の和集合の大きさを計算する方法として、まず |A| と |B| を足しあわせ、それらの積集合の大きさを引き去ることで計算できるというものである。この原理の名称は、あらゆるものを含め、その後で取り除いて補正をするという考え方に基づいていることからきている。n > 2 のときは、積集合の除外計算が場合によって非常に困難になってくる。また、公式には符号が交互にあらわれる。

この公式はアブラーム・ド・モアブルによるものと考えられている。時にジェームス・ジョセフ・シルベスターまたはアンリ・ポアンカレによるとも言われる。

3つの集合について包除を図示

3つの集合 A, B, C に対しての包除原理は右図のようにあらわされる。

[編集] 証明

包除原理を一般に証明するため、X を A₁, ..., A_n の上位集合とする。公式はまず恒等式

$1_{\bigcup_{i=1}^n A_i}=\sum_{i=1}^n 1_{A_i} -\sum_{i,j\,:\,i<j}1_{A_i\cap A_j}$

$+\sum_{i,j,k\,:\,i<j<k}1_{A_i\cap A_j\cap A_k}-\ \cdots\cdots\ \pm 1_{A_1\cap\cdots\cap A_n}$

を指示関数の変形でもとめ、全ての x ∈ X について足しあわせることで示される。

[編集] その他の形

この原理は時に以下のような形で表される。

$g(A)=\sum_{S\,:\,S\subseteq A}f(S)$

としたとき、

$f(A)=\sum_{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)$

この形はAの全ての部分集合からなる半順序集合におけるincidence algebraでのメビウスの反転公式となる。

また、包除原理は確率においても以下のように用いられる。

$\Pr\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n \Pr\left(A_i\right) -\sum_{i,j\,:\,i<j}\Pr\left(A_i\cap A_j\right)$ $+\sum_{i,j,k\,:\,i<j<k}\Pr\left(A_i\cap A_j\cap A_k\right)-\ \cdots\cdots\ \pm \Pr\left(\bigcap_{i=1}^n A_i\right).$

ボンフェローニの不等式によれば、この公式の始めの k 項の和は左辺の上界と下界を交互にとる。このことは公式全体が扱いにくい場合に利用される。

[編集] 応用

おそらく、包除原理のもっともよく知られている応用は、組み合わせ問題における有限集合の攪乱(derangement)に対するものであろう。集合Aの攪乱とはAから自分自身への全単射であって不動点を持たないもののことである。包除原理によって、Aの基数（要素数）をnとしたときの攪乱の数が

$\left [ \frac {n!}{e} \right ]$

となることを示せる。ここで[x]はもっとも近い整数をあたえる関数(nearest integer function)を表す。

これはnのsubfactorialとしても知られ、 $!n$ と表す。これはまた、全ての全単射に等しい確率が与えられた場合、無作為に選ばれた全単射が攪乱となっている確率がnの増加に従い、1/e に素早く近づくことを示している。

この原理によって理論的な公式を求める場合（特にエラトステネスの篩を用いる素数の数え上げ）、誤差評価が困難であるため有効な公式が得られないことが多い。これは、各項が個別には正確に求められてもそれらの相殺の様子を一般的に定式化することが難しい上に、和の項数が非常に多くなってしまうためである。数論において、ヴィーゴ・ブルンはこのような困難を部分的に克服する方法を見出し、これは現代的な篩の理論の端緒となった。ただし、この理論を用いてもたいてい、厳密な公式はもとより漸近公式さえ得られるのもまれで、したがってふるい落とされた集合の大きさの評価を与えるにとどまる。