包除原理
包除原理（ほうじょげんり、英: Inclusion-exclusion principle, principle of inclusion and exclusion, Principle of inclusion-exclusion, PIE）あるいは包含と排除の原理とは、数え上げ組合せ論における基本的な結果のひとつ。特別な場合には「有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する元の数 |A ∩ B| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。
以上の2つの有限集合 A, B に対する包除原理は次のように表せる。
- [math]\begin{align} \left| A \cup B \right| = &\left| A \right| + \left| B \right| - \left| A \cap B \right| \\ \end{align}[/math]
同様に、3つの有限集合 A, B, C に対する包除原理は次のように表せる。
- [math]\begin{align} \left| A \cup B \cup C \right| = &\left| A \right| + \left| B \right| + \left| C \right| \\ &\quad - \left| A \cap B \right| - \left| B \cap C \right| - \left| C \cap A \right| \\ &\qquad + \left| A \cap B \cap C \right| \end{align}[/math]
一般に、 n 個の有限集合 A1, ..., An が与えられたとき、その和集合に属する元の数は
- [math]\begin{align} \left\vert \bigcup_{i =1}^n A_i \right\vert &= \sum_{k=1}^n (-1)^{k - 1} \! \sum_{J \subseteq [n],\ \vert J \vert = k} \left\vert \bigcap_{j \in J} A_j \right\vert \\ &= \sum_i \left|A_i\right| - \sum_{i \lt j} \left|A_i\cap A_j\right| + \cdots + (-1)^{n - 1} \left|A_1\cap \cdots \cap A_n\right| \end{align}[/math]
と表せる[1][2]。ただし、ここで [n] = {1, 2, …, n} とした。
この原理の名称は、あらゆるものを「含め」、その後で「取り除いて」補正をするという考え方に基づいていることからきている。n > 2 のとき、共通部分の補正項を計算するのが非常に困難になることもある。また、公式には符号が交互にあらわれる。
この公式はアブラーム・ド・モアブルによるものと考えられている。時にジェームス・ジョセフ・シルベスターまたはアンリ・ポアンカレによるとも言われる。
証明
包除原理を一般に証明するため、X を A1, ..., An の上位集合とする。公式はまず恒等式
- [math] 1_{\bigcup A_i} = \sum_i 1_{A_i} -\sum_{i \lt j}1_{A_i \cap A_j} + \cdots + (-1)^{n - 1} 1_{\bigcap A_i} [/math]
を指示関数の変形でもとめ、全ての x ∈ X について足しあわせることで示される。
その他の形
この原理は時に以下のような形で表される。
- [math]g(A)=\sum_{S\,:\,S\subseteq A}f(S)[/math]
としたとき、
- [math]f(A)=\sum_{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)[/math]
この形はAの全ての部分集合からなる半順序集合における隣接代数でのメビウスの反転公式となる。
また、包除原理は確率においても以下のように用いられる。
- [math] \Pr\left(\bigcup_i A_i\right) = \sum_i \Pr\left(A_i\right) - \sum_{i \lt j} \Pr\left(A_i\cap A_j\right) + \cdots + (-1)^{n - 1} \Pr\left(\bigcap_i A_i\right) [/math]
ボンフェローニの不等式によれば、この公式の始めの k 項の和は左辺の上界と下界を交互にとる。このことは公式全体が扱いにくい場合に利用される。
応用
おそらく、包除原理のもっともよく知られている応用は、組み合わせ問題における有限集合の攪乱(derangement)に対するものであろう。集合Aの攪乱とはAから自分自身への全単射であって不動点を持たないもののことである。包除原理によって、Aの基数（要素数）をnとしたときの攪乱の数が
- [math]\left [ \frac {n!}{e} \right ][/math]
となることを示せる。ここで[x]はもっとも近い整数をあたえる関数(nearest integer function)を表す。
これはnのsubfactorialとしても知られ、[math]!n[/math]と表す。 これはまた、全ての全単射に等しい確率が与えられた場合、無作為に選ばれた全単射が攪乱となっている確率がnの増加に従い、1/e に素早く近づくことを示している。
この原理によって理論的な公式を求める場合（特にエラトステネスの篩を用いる素数の数え上げ）、誤差評価が困難であるため有効な公式が得られないことが多い。これは、各項が個別には正確に求められてもそれらの相殺の様子を一般的に定式化することが難しい上に、和の項数が非常に多くなってしまうためである。数論において、ヴィーゴ・ブルンはこのような困難を部分的に克服する方法を見出し、これは現代的な篩の理論の端緒となった。ただし、この理論を用いてもたいてい、厳密な公式はもとより漸近公式さえ得られるのもまれで、したがってふるい落とされた集合の大きさの評価を与えるにとどまる。
共通部分の計算
包除原理とド・モルガンの法則とを合わせることで、共通部分の要素数を計算できる。[math]A[/math] を普遍集合、各 [math]i[/math] について [math]A_i \subseteq A[/math] とし、[math]\overline{A_i}[/math] が [math]A[/math] に関する [math]A_i[/math] の補集合を表すものとする。このとき
[math] \left \vert \bigcap_{i=1}^n A_i \right \vert = \overline{\left \vert \bigcup_{i=1}^n \overline{A_i} \right \vert}[/math]
をえる。こうして、共通部分をもとめる問題を和集合をもとめる問題に帰着させることができる。
脚注
参考文献
- 西岡康夫 『数学チュートリアル やさしく語る 確率統計』 オーム社、2013年。ISBN 9784274214073。
- 伏見康治 『確率論及統計論』 河出書房、1942年。ISBN 9784874720127。
- 日本数学会 『数学辞典』 岩波書店、2007年、第4版。ISBN 9784000803090。