包除原理

包除原理

包除原理（ほうじょげんり、英: Inclusion-exclusion principle）は、数え上げ組合せ論の基本的な法則の一つで、特に有限集合の元の数を求める際に用います。この原理は、集合の元を数え上げる際に重複を排除する方法を示します。

原理の説明

2つの有限集合AとBを考えた場合、和集合に属する元の数、すなわち|A ∪ B|は次のように計算されます。

$$
$$

この式の解釈は、最初にそれぞれの集合に含まれる元の数を単純に足し合わせ、共通部分の元の数を引くことによって、重複を除去するというものです。

同様に、3つの集合A、B、およびCの場合は、次のように扱います。

$$
$$

一般的に、n個の有限集合A1, A2, ..., Anに対する包除原理は、以下の式で表されます。

$$
$$

ここで、Jは集合の部分集合を表します。この原理の名称は、まず全てを「含め」、次に重複する部分を「取り除く」といった考え方からきています。

証明

包除原理の証明では、XをA1, A2, ..., Anの上位集合とし、指示関数を用いて元の数を表現し、すべてのx ∈ Xに対して足しあわせる方法が採用されます。この過程で、和集合や共通部分を利用し、包除原理の恒等式を導き出します。

他の形式

この原理は、集合のべき集合に対しても適用可能であり、もしある関数fとgについて特定の性質が成り立つならば、次のような式が得られます。

$$
f(A) = ∑_{B ⊆ A} (-1)^{|A ackslash B|} g(B)
$$

さらに、確率論での応用として、n個の事象の和の確率についても包除原理が使われます。この場合、事象が同時に発生する確率を加算し、重複を防ぐための補正項が引かれます。

応用

包除原理は、特に組み合わせ問題での応用が顕著であり、特定の集合の攪乱（derangement）数を算出する際に用いられます。これは、枚挙や確率における重要な道具立てになっており、数理モデルの構築や解析に貢献しています。

まとめ

包除原理は、集合論や確率論、組み合わせ論において非常に重要な役割を果たします。その利用方法は多岐にわたり、具体的な計算から理論的な応用までを含んでいます。

参考文献

• - 西岡康夫『数学チュートリアル やさしく語る 確率統計』オーム社（2013年）
• - 日本数学会『数学辞典』（第4版）岩波書店（2007年）

もう一度検索