包除原理のソースを表示

'''包除原理'''（ほうじょげんり、{{lang-en-short|Inclusion-exclusion principle, principle of inclusion and exclusion, Principle of inclusion-exclusion, PIE}}）あるいは包含と排除の原理とは、[[数え上げ組合せ論]]における基本的な結果のひとつ。特別な場合には「[[有限集合]] ''A'' と ''B'' の[[合併 (集合論)|和集合]]に属する[[濃度 (数学)|元の数]]を計算するには、まずそれぞれに属する元の数 |''A''| と |''B''| を足しあわせた後、それらの[[共通部分 (数学)|共通部分]]に属する元の数 |''A'' &cap; ''B''| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。

[[File:Intersection of sets A and B.svg|right|200px]]
以上の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>
[[画像:Inclusion-exclusion.png|thumb|200px|3つの集合について包除を図示]]

一般に、 ''n'' 個の有限集合 ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> が与えられたとき、その和集合に属する元の数は
:<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 < j} \left|A_i\cap A_j\right|
        + \cdots
        + (-1)^{n - 1} \left|A_1\cap \cdots \cap A_n\right|
\end{align}</math>
と表せる{{sfn|数学辞典|2007|loc=63. 数え上げ理論}}{{sfn|西岡|2013|loc=4.4 包除原理|p={{google books quote|id=AUY2AgAAQBAJ|page=50|50}}}}。ただし、ここで [''n''] = {1, 2, &hellip;, ''n''} とした。

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

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

==証明==
包除原理を一般に証明するため、''X'' を ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> の[[部分集合#定義|上位集合]]とする。公式はまず恒等式

:<math>
 1_{\bigcup A_i}
 =
 \sum_i 1_{A_i}
 -\sum_{i < j}1_{A_i \cap A_j}
 + \cdots
 + (-1)^{n - 1} 1_{\bigcap A_i}
</math>

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

==その他の形==
この原理は時に以下のような形で表される{{sfn|Gessel|Stanley|1995|p={{google books quote|id=ZyvpoazU-O0C|page=1049|1049}}}}。有限集合 ''S'' の[[べき集合]] 2<sup>''S''</sup> 上で定義された関数 ''f'', ''g'' が

:<math>g(A)=\sum_{B \subseteq A}f(B)</math>

を満たすならば、

:<math>f(A)=\sum_{B\subseteq A}(-1)^{\left|A \setminus B\right|}g(B).</math>

この形は[[半順序集合]] 2<sup>''S''</sup> の[[隣接代数 (順序理論)|隣接代数]]における[[メビウス関数|メビウスの反転公式]]となる。

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

:<math>
 \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)
</math>

{{仮リンク|ボンフェローニの不等式|en|Boole%27s_inequality#Bonferroni_inequalities}}によれば、この公式の始めの ''k'' 項の和は左辺の[[順序集合#上界、最大、極大、上限、上方集合|上界]]と[[順序集合#上界、最大、極大、上限、上方集合|下界]]を交互にとる{{sfn|Galambos|2001}}：
:<math>\begin{align}
 \Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right), \\
 \Pr\left(\bigcup_i A_i\right) &\ge \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right), \\
 \Pr\left(\bigcup_i A_i\right) &\le \sum_i \Pr\left(A_i\right) - \sum_{i < j} \Pr\left(A_i\cap A_j\right) + \sum_{i < j<k} \Pr\left(A_i\cap A_j\cap A_k\right), \\
 &\vdots
\end{align}</math>
このことは公式全体が扱いにくい場合に利用される。

==応用==
おそらく、包除原理のもっともよく知られている応用は、組み合わせ問題における有限集合の攪乱([[完全順列|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>

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

== 脚注 ==
{{reflist|2}}

== 参考文献 ==
* {{Cite book|和書|author=西岡康夫|year=2013|title=数学チュートリアル やさしく語る 確率統計|publisher=[[オーム社]]|isbn=978-4-274-21407-3|url={{google books|AUY2AgAAQBAJ|plainurl=yes}}|ref={{sfnref|西岡|2013}}}}
* {{Cite book|和書|author=伏見康治|authorlink=伏見康治|origyear=1942|date=2002-12-10|title=確率論および統計論|edition=復刻版再発行|publisher=現代工学社|isbn=978-4-87472-012-7|url=https://web.archive.org/web/20130503002149/http://ebsa.ism.ac.jp/ebooks/ebook/204| ref={{sfnref|伏見|2002}}}}
* {{Cite book|和書|author=日本数学会|authorlink=日本数学会|year=2007|title=数学辞典|edition=第4版|publisher=[[岩波書店]]|isbn=978-4-00-080309-0|ref={{sfnref|数学辞典|2007}}}}
* {{citation
    |editor1-last      = Graham
    |editor1-first     = R. L.
    |editor1-link      = 
    |editor2-last      = Grötschel
    |editor2-first     = M.
    |editor2-link      = 
    |editor3-last      = Lovász
    |editor3-first     = L.
    |editor3-link      = ラースロー・ロヴァース
    |year              = 1995
    |title             = Handbook of Combinatorics
    |last1             = Gessel
    |first1            = Ira M.
    |authorlink1       = 
    |last2             = Stanley
    |first2            = Richard P.
    |authorlink2       = 
    |contribution      = Algebraic enumeration
    |pages             = 1021–1061
    |volume            = II
    |url               = {{google books|ZyvpoazU-O0C|plainurl=yes|page=1021}}
    |publisher         = MIT Press
    |isbn              = 978-0-444-88002-4
    |mr                = 1373655
    |zbl               = 
}}
== 関連項目 ==
{{Div col}}
*[[完全順列]]
*[[集合]]
*[[集合論]]
*[[ベン図]]
{{Div col end}}

== 外部リンク ==
*{{高校数学の美しい物語|611|包除原理の２通りの証明}}
*{{MathWorld|title=Inclusion-Exclusion Principle|urlname=Inclusion-ExclusionPrinciple}}
* {{SpringerEOM |title=Inclusion-and-exclusion principle |id=Inclusion-and-exclusion_principle |last=Rukova |first=S.A. |ref={{sfnref|Rukova|2001}}}}
* {{SpringerEOM |title=Bonferroni inequalities |id=Bonferroni_inequalities |last=Galambos |first=J. |ref={{sfnref|Galambos|2001}}}}
----

{{PlanetMath attribution|id=32803|title=principle of inclusion-exclusion}}

{{DEFAULTSORT:ほうしよけんり}}
[[Category:組合せ論]]
[[Category:数学の原理]]
[[Category:数学に関する記事]]