包除原理

同義語：包含と除去の原理inclusion–exclusion principleprinciple of inclusion and exclusion

概要

前提知識: 有限集合, 和集合, 共通部分, 二項係数

$1$ から $30$ までの整数のうち、$2,3,5$ のどれでも割り切れないものは何個あるか。$2$ の倍数は $15$ 個、$3$ の倍数は $10$ 個、$5$ の倍数は $6$ 個あるが、$30-(15+10+6)=-1$ とすると $6$ の倍数のように 2 回引かれた数があるので、$6,10,15$ の倍数の個数 $5,3,2$ を足し戻す。すると今度は $30$ が「3 回引いて 3 回足した」ので $1$ 回も引かれていないことになり、最後に $1$ を引く。こうして
$$ 30-(15+10+6)+(5+3+2)-1=8 $$
を得る。実際、該当する数は $1,7,11,13,17,19,23,29$ の 8 個である。このように、重なりを持つ集まりの大きさを「足しすぎたら引き、引きすぎたら足す」ことで正確に数える原理が 包除原理 である。同じ考え方で、4 人が預けた帽子をだれも自分の帽子を受け取らないように返す方法は $4!-4\cdot3!+6\cdot2!-4\cdot1!+1=9$ 通りと数えられる（ex-ie-hats）。
包除原理は有限集合の元の個数についての最も基本的な公式の一つであり、Eulerのφ関数の公式、完全順列（順列）の個数、全射の個数、篩法による素数の数え上げ、確率の計算などに使われる。一般形の等式とその証明は数え上げ組合せ論の記事の定理「包除の等式」にもある。本記事では、一般の読者向けに言明と証明を述べたうえで、途中で打ち切ったときの大小（Bonferroni の不等式）と、応用の型を扱う。

定義

以下、$X$ を有限集合、$A_1,\dots,A_m$ を $X$ の部分集合とし、有限集合 $A$ の元の個数を $|A|$ と書く。$1\le i_1<\dots< i_k\le m$ について $A_{i_1}\cap\cdots\cap A_{i_k}$ を「$k$ 個ずつの共通部分」と呼ぶ。

共通部分の大きさの和

$k=1,\dots,m$ について
$$ S_k:=\sum_{1\le i_1< i_2<\cdots< i_k\le m}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}| $$
とおく。$S_k$ は $k$ 個ずつの共通部分 $\binom mk$ 個の大きさの和である。$S_0:=|X|$ と約束する。

$S_1=|A_1|+\cdots+|A_m|$、$S_2=\sum_{i< j}|A_i\cap A_j|$、$S_m=|A_1\cap\cdots\cap A_m|$ である。冒頭の例では $X=\{1,\dots,30\}$、$A_1,A_2,A_3$ をそれぞれ $2,3,5$ の倍数の集合として、$S_1=31$、$S_2=10$、$S_3=1$ である。

包除原理の等式

$$ |A_1\cup A_2\cup\cdots\cup A_m|=S_1-S_2+S_3-\cdots+(-1)^{m-1}S_m=\sum_{k=1}^m(-1)^{k-1}S_k $$
が成り立つ。同じことを補集合で言えば、どの $A_i$ にも属さない $X$ の元の個数は
$$ |X\setminus(A_1\cup\cdots\cup A_m)|=S_0-S_1+S_2-\cdots+(-1)^mS_m=\sum_{k=0}^m(-1)^kS_k $$
である。

各元が何回数えられるか

右辺の和で、$X$ の各元 $x$ が何回数えられるかを調べる。$x$ がちょうど $j$ 個の $A_i$ に属するとする。$x$ が $k$ 個ずつの共通部分 $A_{i_1}\cap\cdots\cap A_{i_k}$ に属するのは、$i_1,\dots,i_k$ がすべて $x$ を含む $j$ 個の添字から選ばれているときに限るので、$x$ は $S_k$ の中でちょうど $\binom jk$ 回数えられる（$k>j$ なら $\binom jk=0$）。
$j=0$ なら $x$ はどの $S_k$（$k\ge1$）にも現れず、左辺の和集合にも属さない。$j\ge1$ なら、$x$ が右辺で数えられる回数は、二項定理 $(1-1)^j=\sum_{k=0}^j(-1)^k\binom jk=0$ により
$$ \sum_{k=1}^j(-1)^{k-1}\binom jk=1-\sum_{k=0}^j(-1)^k\binom jk=1 $$
であり、$x$ は左辺の和集合に属して 1 回数えられる。すべての元について両辺で数えられる回数が一致するので、第 1 の等式が成り立つ。第 2 の等式は、$|X\setminus U|=|X|-|U|$（$U$ は和集合）に第 1 の等式を代入したものである。$\square$

同じ等式の、添字集合の上の全単射で符号を打ち消し合わせる証明は数え上げ組合せ論の記事の定理「包除の等式」に、$m$ についての帰納法による証明は KT17 の Theorem 7.7（p. 145）にある。

直感

$m=2$ のとき等式は $|A\cup B|=|A|+|B|-|A\cap B|$ である。$|A|+|B|$ では両方に属する元が 2 回数えられているので、その分 $|A\cap B|$ を 1 回引く（和集合の記事の命題「二集合の包除原理」、Ham Fact 3.6、p. 93）。$m=3$ では
$$ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C| $$
となる。3 つの円を重ねた図（Venn 図）で、3 つすべてに属する中央の部分は、1 段目で 3 回足され、2 段目で 3 回引かれ、3 段目で 1 回足されて、合計 1 回になる。一般に、ちょうど $j$ 個の集合に属する元は $\binom j1-\binom j2+\binom j3-\cdots$ 回数えられ、これが常に $1$ になることが包除原理の中身である。
包除原理が役に立つのは、和集合の大きさを直接数えるのは難しいが、共通部分の大きさは数えやすい場合である。「$2$ でも $3$ でも割り切れる」は「$6$ で割り切れる」と言い換えられ、「$1$ 番と $2$ 番の人が自分の帽子を受け取る」並べ方は残りの人の並べ方として数えられる。「どれか 1 つの条件を満たす」より「指定したいくつかの条件をすべて満たす」ほうが数えやすいのである。

例と反例

帽子の返し方

4 人 $1,2,3,4$ が預けた帽子を 1 つずつ返す方法は $4!=24$ 通りある。$A_i$ を「$i$ 番の人が自分の帽子を受け取る」返し方の集合とすると、指定した $k$ 人が自分の帽子を受け取る返し方は、残りの $4-k$ 人の帽子の返し方なので $(4-k)!$ 通りであり、$S_k=\binom4k(4-k)!=4!/k!$ である。だれも自分の帽子を受け取らない返し方は、thm-ie-main の補集合の形により
$$ 24-24+12-4+1=9 $$
通りである。一般に $n$ 人では $D_n=n!\sum_{k=0}^n(-1)^k/k!$ 通りであり（数え上げ組合せ論の記事の例「完全順列の個数」）、$D_1,\dots,D_6=0,1,2,9,44,265$ である。

上限つきの個数の配り方

$x_1+x_2+x_3=10$ を満たす $0$ 以上の整数の組は、10 個の玉と 2 本の仕切りの並べ方として $\binom{12}2=66$ 個ある（重複組合せ、二項定理と組合せの恒等式）。このうち各 $x_i\le4$ を満たすものを数える。$A_i$ を $x_i\ge5$ となる組の集合とすると、$A_1$ の組は $x_1'=x_1-5$ とおけば $x_1'+x_2+x_3=5$ の解と 1 対 1 に対応するので $|A_i|=\binom72=21$、$A_i\cap A_j$（$i\ne j$）は $x_i'+x_j'+x_l=0$ の解で $\binom22=1$ 個、3 つの共通部分は $15>10$ なので空である。よって求める個数は
$$ 66-3\cdot21+3\cdot1-0=6 $$
であり、実際 $(4,4,2)$ と $(4,3,3)$ の並べ替え $3+3=6$ 個である（Lev §3.8.2、pp. 291–295 に同じ型の問題がある）。

反例：途中で打ち切ると過不足が出る

冒頭の例で、$2,3,5$ の少なくとも 1 つで割り切れる $30$ 以下の正の整数は $30-8=22$ 個である。包除の和を途中で打ち切ると
$$ S_1=31>22,\qquad S_1-S_2=21<22,\qquad S_1-S_2+S_3=22 $$
となり、最後まで足したときに初めて正しい値になる。$S_1$ だけの近似は、集合が互いに交わらないという仮定のもとでの公式 $|A_1\cup\cdots\cup A_m|=|A_1|+\cdots+|A_m|$（和の法則）であり、この例はその仮定を破っている。打ち切った和は正しい値を上と下から交互に挟む（thm-ie-bonferroni）。

反例：無限集合では引き算が意味をもたない

$A=B=\mathbb{N}$ では $|A\cup B|$、$|A|$、$|B|$、$|A\cap B|$ はすべて無限であり、$|A|+|B|-|A\cap B|$ の「無限 $-$ 無限」は定まらない。包除原理は集合が有限であるという仮定を使っている（prf-ie-main で各元の数えられる回数を足し合わせるところ）。無限集合でも、全体に確率（確率空間）や測度のような有限の量を割り当てれば、同じ形の等式が成り立つ（rem-ie-probability）。

性質

Bonferroni の不等式

二項係数の交代和の打ち切り

整数 $j\ge1$、$r\ge0$ について
$$ \sum_{k=0}^r(-1)^k\binom jk=(-1)^r\binom{j-1}r $$
である（$r\ge j$ なら両辺とも $0$）。

Pascal の漸化式で打ち消し合う

$r$ についての帰納法で示す。$r=0$ なら両辺とも $1$ である。$r\ge1$ とし、$r-1$ で成り立つとすると、Pascal の漸化式 $\binom jr=\binom{j-1}r+\binom{j-1}{r-1}$（二項係数）により
$$ \sum_{k=0}^r(-1)^k\binom jk=(-1)^{r-1}\binom{j-1}{r-1}+(-1)^r\Bigl(\binom{j-1}r+\binom{j-1}{r-1}\Bigr)=(-1)^r\binom{j-1}r $$
である。$r\ge j$ なら $\binom{j-1}r=0$ である。$\square$

Bonferroniの不等式

$U:=A_1\cup\cdots\cup A_m$、$1\le r\le m$ とし、包除の和を $r$ 項で打ち切ったものを $T_r:=\sum_{k=1}^r(-1)^{k-1}S_k$ とする。$r$ が奇数なら $|U|\le T_r$、$r$ が偶数なら $|U|\ge T_r$ である。特に
$$ |U|\le S_1,\qquad |U|\ge S_1-S_2,\qquad |U|\le S_1-S_2+S_3 $$
である。

打ち切った和での数えられる回数

prf-ie-main と同じく、ちょうど $j$ 個の $A_i$ に属する元 $x$ が $T_r$ で数えられる回数を調べる。$j=0$ なら $0$ 回で、$x\notin U$ である。$j\ge1$ なら、lem-ie-alternating により
$$ \sum_{k=1}^r(-1)^{k-1}\binom jk=1-\sum_{k=0}^r(-1)^k\binom jk=1-(-1)^r\binom{j-1}r $$
回である。$r$ が奇数ならこれは $1+\binom{j-1}r\ge1$、偶数なら $1-\binom{j-1}r\le1$ である。$x\in U$ は $|U|$ で 1 回数えられるので、すべての元について足し合わせると、$r$ が奇数なら $T_r\ge|U|$、偶数なら $T_r\le|U|$ である。$\square$

$r=m$ では $\binom{j-1}m=0$（$j\le m$）なので等号になり、thm-ie-main が再び得られる。$r=1$ の $|U|\le S_1$ は「和集合の大きさは大きさの和以下」という最も粗い評価であり、確率では Boole の不等式と呼ばれる。項の数が多く全部を計算できないとき、Bonferroni の不等式は途中までの和で真の値を上下から挟むことを保証する（Sho08 Chapter 8 の Exercise 8.4、p. 213）。

素数で割り切れない数の個数と Euler の φ 関数

素数で割り切れない数の個数

$N\ge1$ を整数、$p_1,\dots,p_k$ を相異なる素数とする。$1$ 以上 $N$ 以下の整数のうち、どの $p_i$ でも割り切れないものの個数は
$$ \sum_{I\subset\{1,\dots,k\}}(-1)^{|I|}\Bigl\lfloor\frac{N}{\prod_{i\in I}p_i}\Bigr\rfloor $$
である（$I=\emptyset$ の項は $N$）。特に $N$ がすべての $p_i$ で割り切れるなら、この個数は $N\prod_{i=1}^k\bigl(1-\frac1{p_i}\bigr)$ に等しい。

同時に割り切れることは積で割り切れること

$X=\{1,\dots,N\}$、$A_i$ を $p_i$ の倍数の集合とする。$I\ne\emptyset$ について、$a$ がすべての $p_i$（$i\in I$）で割り切れることは、$\prod_{i\in I}p_i$ で割り切れることと同値である（相異なる素数の積なので、素因数分解の一意性による）。よって $\bigcap_{i\in I}A_i$ は $\prod_{i\in I}p_i$ の倍数の集合であり、その大きさは床関数の記事の命題「倍数の個数」により $\lfloor N/\prod_{i\in I}p_i\rfloor$ である。thm-ie-main の補集合の形から最初の式を得る。
$N$ がすべての $p_i$ で割り切れるなら、床を外して $N/\prod_{i\in I}p_i$ としてよく、和は積の展開
$$ \sum_{I}(-1)^{|I|}\prod_{i\in I}\frac1{p_i}=\prod_{i=1}^k\Bigl(1-\frac1{p_i}\Bigr) $$
の $N$ 倍になる。$\square$

$n\ge2$ の相異なる素因数を $p_1,\dots,p_k$ とし、$N=n$ とすると、$1$ 以上 $n$ 以下で $n$ と互いに素な数は、どの $p_i$ でも割り切れない数と一致する。よって
$$ \varphi(n)=n\prod_{i=1}^k\Bigl(1-\frac1{p_i}\Bigr) $$
を得る。たとえば $\varphi(60)=60\cdot\frac12\cdot\frac23\cdot\frac45=16$ である。これは Eulerのφ関数の記事の定理「素因数分解による公式」の、乗法性を使わない別の証明である（Mos11 Chapter 2、p. 9。KT17 Theorem 7.14、p. 150）。$N$ が割り切れない場合の例として、$1$ から $1000$ までで $2,3,5,7$ のどれでも割り切れない数は
$$ 1000-(500+333+200+142)+(166+100+71+66+47+28)-(33+23+14+9)+4=228 $$
個である。この 228 個には $121=11^2$ のような合成数も含まれるが、$\sqrt{1000}<32$ なので、$31$ 以下の素数 11 個すべてについて同じ計算をすれば、残るのは $1$ と、$31$ より大きく $1000$ 以下の素数だけになり、素数の個数が求まる（素数の記事の命題「素因数の存在」の 2 による）。この方法を一般化したものが数え上げ組合せ論の記事の例「指定した素数の倍数を除く」と篩法である。

完全順列と全射

ex-ie-hats の一般の場合、すなわち $\{1,\dots,n\}$ の置換で不動点をもたないもの（完全順列）の個数 $D_n=n!\sum_{k=0}^n(-1)^k/k!$ は、包除原理のもっとも有名な応用である。この式から、でたらめに帽子を返したときにだれも自分の帽子を受け取らない確率が、人数によらずほぼ一定であることがわかる。

完全順列の個数と $\frac{1}{e}$

$n\ge1$ について、$D_n$ は $n!/e$ に最も近い整数であり、$|D_n-n!/e|<\frac1{n+1}$ である。特に $D_n/n!\to1/e=0.3678\ldots$（$n\to\infty$）である。

交代級数の残りを評価する

指数関数の級数表示 $e^{-1}=\sum_{k=0}^\infty(-1)^k/k!$ により
$$ \frac{n!}e-D_n=n!\sum_{k=n+1}^\infty\frac{(-1)^k}{k!}=(-1)^{n+1}n!\Bigl(\frac1{(n+1)!}-\frac1{(n+2)!}+\frac1{(n+3)!}-\cdots\Bigr) $$
である。括弧の中の級数の項は絶対値が単調に減少して $0$ に近づくので、隣り合う 2 項ずつまとめると $\bigl(\frac1{(n+1)!}-\frac1{(n+2)!}\bigr)+\bigl(\frac1{(n+3)!}-\frac1{(n+4)!}\bigr)+\cdots>0$ であり、最初の項を残して 2 項ずつまとめると $\frac1{(n+1)!}-\bigl(\frac1{(n+2)!}-\frac1{(n+3)!}\bigr)-\cdots<\frac1{(n+1)!}$ である。よって括弧の値は $0$ より大きく $\frac1{(n+1)!}$ より小さく、$|n!/e-D_n|<\frac{n!}{(n+1)!}=\frac1{n+1}\le\frac12$ である。$D_n$ は整数なので $n!/e$ に最も近い整数である。$n!$ で割ると $|D_n/n!-1/e|<\frac1{(n+1)!}\to0$ である。$\square$

$n=4$ では $4!/e=8.829\ldots$ で $D_4=9$、$n=10$ では $D_{10}/10!=1334961/3628800=0.3678794\ldots$ であり、$1/e=0.3678794\ldots$ と小数第 7 位まで一致する（KT17 Theorem 7.11・7.12、pp. 147–148）。
写像の数え上げにも同じ形が現れる。$n$ 元集合から $k$ 元集合への全射の個数は、「値 $i$ をとらない」写像の集合を $A_i$ として $\sum_{j=0}^k(-1)^j\binom kj(k-j)^n$ であり（数え上げ組合せ論の記事の命題「全射の個数と明示式」）、たとえば $4$ 元集合から $3$ 元集合への全射は $81-3\cdot16+3\cdot1-0=36$ 個である。

補足

確率での形

有限個の事象 $A_1,\dots,A_m$ をもつ確率空間では、個数を確率に置き換えた
$$ P(A_1\cup\cdots\cup A_m)=\sum_{k=1}^m(-1)^{k-1}\sum_{i_1<\cdots< i_k}P(A_{i_1}\cap\cdots\cap A_{i_k}) $$
が成り立ち、Bonferroni の不等式も同じ形で成り立つ。有限または可算の確率空間では、各元（根元事象）がその確率の重みで数えられると考えれば、prf-ie-main と prf-ie-bonferroni がそのまま証明になる（Sho08 §8.1 の Theorem 8.1、p. 210。Bonferroni の不等式は Chapter 8 の Exercise 8.4、p. 213）。一様な確率では両辺を $|X|$ 倍すれば thm-ie-main に戻る。

関数による形と Möbius 関数への一般化

包除原理は、部分集合の指示関数についての恒等式 $\mathbf 1_{X\setminus(A_1\cup\cdots\cup A_m)}=\prod_{i=1}^m(1-\mathbf 1_{A_i})$ を展開して各元で足し合わせたものとも見られる（特性関数(集合) の記事の定理「包除原理の関数形」）。また、部分集合の包含関係がつくる半順序集合の Möbius 関数が $(-1)^{|I|}$ であることから、包除原理は半順序集合の上の Möbius の反転公式の特別な場合になる（Möbiusの反転公式の記事の定理「包除原理」、数え上げ組合せ論の記事の節「Möbius 関数による一般化された包除」）。整数の約数の順序に移すと、prop-ie-coprime-count の符号 $(-1)^{|I|}$ は Möbius関数の値 $\mu(\prod_{i\in I}p_i)$ にほかならない。

文献

2 個の集合の場合は Ham §3.7 の Fact 3.6（p. 93）、2 個の場合（Theorem 3.3.4）・3 個の場合（Theorem 3.3.6）と 4 個の場合の式は Lev §3.3.3（p. 223、4 個の場合は pp. 224–225。一般の $m$ 個についての式そのものは述べていない）、応用（重複組合せの上限・完全順列・全射）は Lev §3.8（pp. 290–301、完全順列は pp. 315–316、全射は pp. 316–321）にある。KT17 Chapter 7 は一般形の帰納法による証明（Theorem 7.7、p. 145）、全射（Theorem 7.9、p. 146）、完全順列（Theorem 7.11・7.12、pp. 147–148）、Euler の φ 関数（Theorem 7.14、p. 150）を扱う。Mos11 Chapter 2（p. 9）は包除原理を証明なしで述べて Euler の φ 関数の公式を導いている。