包除原理

包除原理（ほうじょげんり、テンプレート:Lang-en-short）あるいは包含と排除の原理とは、数え上げ組合せ論における基本的な結果のひとつ。特別な場合には「有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する元の数 |A ∩ B| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。

以上の2つの有限集合 A, B に対する包除原理は次のように表せる。

\begin{matrix} | A \cup B | = & | A | + | B | - | A \cap B | \end{matrix}

同様に、3つの有限集合 A, B, C に対する包除原理は次のように表せる。

\begin{matrix} | A \cup B \cup C | = & | A | + | B | + | C | \\ - | A \cap B | - | B \cap C | - | C \cap A | \\ + | A \cap B \cap C | \end{matrix}

一般に、 n 個の有限集合 A₁, ..., A_n が与えられたとき、その和集合に属する元の数は

\begin{matrix} | ⋃_{i = 1}^{n} A_{i} | & = \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{J \subseteq [n], | J | = k} | ⋂_{j \in J} A_{j} | \\ = \sum_{i} | A_{i} | - \sum_{i < j} | A_{i} \cap A_{j} | + \dots + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} | \end{matrix}

と表せるテンプレート:Sfn テンプレート:Sfn。ただし、ここで [n] = {1, 2, …, n} とした。

この原理の名称は、あらゆるものを「含め」、その後で「取り除いて」補正をするという考え方に基づいていることからきている。n > 2 のとき、共通部分の補正項を計算するのが非常に困難になることもある。また、公式には符号が交互にあらわれる。

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

証明

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

1_{⋃ A_{i}} = \sum_{i} 1_{A_{i}} - \sum_{i < j} 1_{A_{i} \cap A_{j}} + \dots + (- 1)^{n - 1} 1_{⋂ A_{i}}

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

その他の形

この原理は時に以下のような形で表されるテンプレート:Sfn。有限集合 S のべき集合 2^S 上で定義された関数 f, g が

g (A) = \sum_{B \subseteq A} f (B)

を満たすならば、

f (A) = \sum_{B \subseteq A} (- 1)^{| A ∖ B |} g (B) .

この形は半順序集合 2^S の隣接代数におけるメビウスの反転公式となる。

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

\Pr (⋃_{i} A_{i}) = \sum_{i} \Pr (A_{i}) - \sum_{i < j} \Pr (A_{i} \cap A_{j}) + \dots + (- 1)^{n - 1} \Pr (⋂_{i} A_{i})

テンプレート:仮リンクによれば、この公式の始めの k 項の和は左辺の上界と下界を交互にとるテンプレート:Sfn：

\begin{matrix} \Pr (⋃_{i} A_{i}) & \leq \sum_{i} \Pr (A_{i}), \\ \Pr (⋃_{i} A_{i}) & \geq \sum_{i} \Pr (A_{i}) - \sum_{i < j} \Pr (A_{i} \cap A_{j}), \\ \Pr (⋃_{i} A_{i}) & \leq \sum_{i} \Pr (A_{i}) - \sum_{i < j} \Pr (A_{i} \cap A_{j}) + \sum_{i < j < k} \Pr (A_{i} \cap A_{j} \cap A_{k}), \\ ⋮ \end{matrix}

このことは公式全体が扱いにくい場合に利用される。

応用

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

[\frac{n!}{e}]

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

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

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

共通部分の計算

包除原理とド・モルガンの法則とを合わせることで、共通部分の要素数を計算できる。 $A$ を普遍集合、各 $i$ について $A_{i} \subseteq A$ とし、 $\overline{A_{i}}$ が $A$ に関する $A_{i}$ の補集合を表すものとする。このとき

$| ⋂_{i = 1}^{n} A_{i} | = \overline{| ⋃_{i = 1}^{n} \overline{A_{i}} |}$

をえる。こうして、共通部分をもとめる問題を和集合をもとめる問題に帰着させることができる。

脚注

テンプレート:Reflist

参考文献

外部リンク

テンプレート:PlanetMath attribution

包除原理

目次

証明

その他の形

応用

共通部分の計算

脚注

参考文献

関連項目

外部リンク

ナビゲーションメニュー

包除原理

証明

その他の形

応用

共通部分の計算

脚注

参考文献

関連項目

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー