包除原理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

組合せ数学において、包除原理（ほうじょげんり、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 に素早く近づくことを示している。

この原理によって厳密な公式をえるような場合の多くにおいて、(特に、エラトステネスの篩を用いて素数の数え上げにおいて)、式の項数が非常に多くなってしまい、その公式はあまり意味をなさなくなる。もし、各項が個別には正確に見積もり可能であっても, 誤差が積み重なってしまうため、包除公式は直接適用できない。数論において、このような困難性に対しヴィーゴ・ブルンによる取り組みが行われた。ゆるやかなスタートの後、彼のアイデアはその他の人々によって引き継がれ、多くの様々な篩法が発達した。こうした例では厳密な公式を得るのではなく、むしろ篩われた集合の上界を得ようとしていたと見られる。