ホーム >> 場合の数 >> 包除原理の意味と証明

集合の要素数の数え上げに関する基本的な公式を紹介します.




包除原理とは

和集合の要素数に関する以下の等式を,包除原理といいます.

包除原理: $A_1,A_2,...,A_n$ を有限集合とするとき,次の等式が成り立つ. $$|A_1\cup A_2 \cup \cdots \cup A_n|=\sum_{i=1}^n |A_i|-\sum_{1\le i < j \le n} |A_i\cap A_j|+\sum_{1\le i < j < k \le n} |A_i\cap A_j \cap A_k|-\cdots +(-1)^n |A_1\cap A_2\cap \cdots \cap A_n|$$ ただし,$|X|$ は集合 $X$ の要素の数を表す.

左辺は,$A_1,...,A_n$ の和集合の要素数です.右辺がわかりにくいかもしれません.まず,和の記号の部分ですが,$\sum$ の下にある $1\le i < j \le n$ というのは,『$i,j$ は $i< j$ を満たしながら, $1$ 以上 $n$ 以下の範囲すべてを渡って和をとる』という意味です.たとえば,$n=4$ ならば, $$\sum_{1\le i < j \le 4} |A_i\cap A_j|=|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2\cap A_3|+|A_2\cap A_4|+|A_3\cap A_4|$$ となります.$1\le i < j < k \le n$ というのも同様です.つまり,右辺に現れる項は,$1$ 個の共通部分,$2$ 個の共通部分,$3$ 個の共通部分,...,$n$ 個の共通部分というように,いくつかの共通部分がそれぞれひとつずつ現れます.

そして,右辺の符号は $+$ と $-$ が交互に現れています.

$n=2$ のとき

この場合はよく知られている下の公式になります. $$|A\cup B|=|A|+|B|-|A\cap B|$$

$n=3$ のとき

この場合は,下のような公式になります. $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$ 下のベン図でこの公式を考えてみましょう.
集合が3つのベン図
左辺は,色のついた部分全体の要素数にあたります.$|A|+|B|+|C|$ は赤い領域と青い領域と黄色い領域の和です.このとき,重なっている部分は足しすぎているので,$-|A\cap B|-|A\cap C|-|B\cap C|$ で帳尻を合わせようとします.こうすると,今度は $|A\cap B\cap C|$ の部分が完全に引かれてしまうので,最後に $+|A\cap B\cap C|$ をすれば,左辺と一致します.これがベン図による包除原理の考え方です.

包除原理の証明

$n=3$ の場合で考えた方法を参考にして,包除原理を数え上げと二項定理を用いて証明してみましょう.

証明: $x\in A_1\cup A_2\cup \cdots \cup A_n$ をひとつ選びます.$A_1,...,A_n$ のうち,$x$ を含む集合を $A_{t_1},A_{t_2},...,A_{t_k}$ とします (ただし,$t_1< t_2 < \cdots < t_k$).示すべき等式の左辺と右辺で要素 $x$ が何回計算されているのか (たし合わせに何回現れるのか)を考えます.
左辺は当然 $1$ 回 $+$ の符号で現れます.以下,右辺を考えます.
まず,第一項では,$A_{t_1},A_{t_2},...,A_{t_k}$ を足すときに $x$ を勘定するので,${}_k \mathrm{C} _1$ 回 $+$ の符号で現れます.
つぎに,第二項では,共通部分をとる二つの集合がどちらも $A_{t_1},A_{t_2},...,A_{t_k}$ のいずれかであるときに限り $x$ を勘定するので,${}_k \mathrm{C} _2$ 回 $-$ の符号で現れます.
以下同様に考えると,第 $r$ 項 ($1\le r\le n$) では ${}_k \mathrm{C} _r$ 回 $(-1)^{r+1}$ の符号で現れます. したがって,合計の $x$ の計算は, $${}_k \mathrm{C} _1-{}_k \mathrm{C} _2+\cdots +(-1)^{k+1}{}_k \mathrm{C} _k$$ となります.

いっぽう,二項定理より, $$(1-1)^k={}_k \mathrm{C} _0-{}_k \mathrm{C} _1+{}_k \mathrm{C} _2-\cdots +(-1)^k {}_k \mathrm{C} _k$$ であり,${}_k \mathrm{C} _0=1$ を上式に代入して移項すると, $$1={}_k \mathrm{C} _1-{}_k \mathrm{C} _2+\cdots +(-1)^{k+1}{}_k \mathrm{C} _k$$ を得ます.したがって,等式の左辺と右辺の $x$ の計算回数は一致します.$x$ は任意にとってきているので,等式が示されます.

練習問題

 $100$ 以下の自然数のうち,$3$ または $5$ の倍数である数はいくつあるか.

→solution

$100$ 以下の $3$ の倍数全体の集合を $A$,$100$ 以下の $5$ の倍数全体の集合を $B$ とすると,求めるべきは $|A\cup B|$.
$100=3\times 33+1$ より,$|A|=33$,$100=5\times 20$ より,$|B|=20$ である.$A\cap B$ は $100$ 以下の $15$ の倍数全体の集合で,$100=15\times 6+10$ より,$|A\cap B|=6$.以上から, $$|A\cup B|=|A|+|B|-|A\cap B|=33+20-6=47$$ $47$ 個.

 $8$ つの異なる色のボールを $3$ つの箱 $a,b,c$ に入れる.どの箱も $1$ つ以上のボールが入っているような入れ方は何通りあるか.

→solution

$X$ を$8$ つの異なる色のボールを何の制約もなく $3$ つの箱に入れる入れ方全体の集合とする.
さらに,$A,B,C$ をそれぞれ箱 $a,b,c$ にボールをひとつもいれない入れ方全体の集合とする.求めるべきは, $$|X|-|A\cup B\cup C|$$ である.$|X|=3^8$ である.また,$|A|=|B|=|C|=2^7$,$|A\cap B|=|A\cap C|=|B\cap C|=1$,$|A\cap B \cap C|=0$ より, $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$ $$=3\times 2^7-3+0=3\times 2^7-3$$ よって, $$|X|-|A\cup B\cup C|=3^8-(2^7-3)=6436$$ $6436$通り.