和集合の要素の個数（包含と排除の原理）

和集合の要素の個数（包含と排除の原理）

包含と排除の原理の図

包含と排除の原理の図

全体集合を $U$ とする、2つの集合 $A$、$B$ について \[n(A)=a~,~n(B)=b~,~n(A\cap{B})=p\] であるとすると図のようになるので \[n(A\cap\overline{B})=a-p~,~n(\overline{A}\cap{B})=b-p\] となるのがわかる。これより \begin{align} &n(A\cup{B})\\ =&\ (a-p)+p+(b-p)\\ =&a+b-p\\ =&\ n(A)+n(B)-n(A\cap{B}) \end{align} が成り立ち、これを包含ほうがんと排除はいじょの原理 (principle of inclusion and exclusion) という。

包含と排除の原理（2集合版）

2つの集合 $A$、$B$ に関して \[n(A\cup{B})=n(A)+n(B)-n(A\cap{B})\] が成り立つ。

特に、$A\cap{B}=\emptyset$ のときには、$n(A\cup{B})=n(A)+n(B)$ となる。

吹き出し和集合の要素の個数（包含と排除の原理）

$n(A\cup{B})$ の要素の個数を数えるのに、$n(A)$ と $n(B)$ を加えたのでは、$n(A\cap{B})$ を2回数えたことになる。そこで、余分な1回分の $n(A\cap{B})$ を引くのだと考えると覚えやすい。イメージは図のようになる。

包含と排除の原理のイメージ

包含と排除の原理のイメージ

包含と排除の原理（2集合版）

$U=\{x|xは100以下の自然数\}$ を全体集合とし、$A=\{x|xは3の倍数\}$、$B=\{x|xは5の倍数\}$ とするとき、次の値を求めよ。

  1. $n(A)$
  2. $n(B)$
  3. $n(A\cap{B})$
  4. $n(A\cup{B})$

  1. $100\div3=33$ あまり $1$ より \[A=\{3\times1,~3\times2,~\cdots,~3\times33\}\] となるのがわかる。よって、$n(A)=\boldsymbol{33}$ である。
  2. $100\div5=20$ より \[B=\{5\times1,~5\times2,~\cdots,~5\times20\}\] となるのがわかる。よって、$n(B)=\boldsymbol{20}$ である。

  3. $A\cap{B}$ は、$3$ の倍数でかつ $5$ の倍数の集合だから、結局 $15$ の倍数の集合である。

    $100\div15=6$ あまり $10$ より \[A\cap{B}=\{15\times1,~15\times2,~\cdots,~15\times6\}\] となるのがわかる。よって、$n(A\cap{B})=\boldsymbol{6}$ である。

  4. 和集合の要素の個数に関して
    $\blacktriangleleft$ 包含と排除の原理（2集合版）参照
    \[n(A\cup{B})=n(A)+n(B)-n(A\cap{B})\] が成り立つから、1～3より \[n(A\cup{B})=33+20-6=\boldsymbol{47}\]

暗記包含と排除の原理（3集合版）の導出

2つの集合に関する包含と排除の原理 \[n(A\cup{B})=n(A)+n(B)-n(A\cap{B})\] を使い、3つの集合に関する包含と排除の原理 \begin{align} &n(A\cup{B}\cup{C})\\ =&\ n(A)+n(B)+n(C)\\ &\quad-n(A\cap{B})-n(B\cap{C})-n(C\cap{A})\\ &\quad+n(A\cap{B}\cap{C}) \end{align} が成り立つのを証明せよ。

\begin{align} &n(A\cup{B}\cup{C})\\ =&n\{(A\cup{B})\cup{C}\}\\ =&n(A\cup{B})+n(C)-n\{(A\cup{B})\cap{C}\}\\ &\blacktriangle~A\cup{B}を1かたまりとして、\\ &\quad『包含と排除の原理（2集合版）』を使った\\ =&\underbrace{n(A\cup{B})}_{\bigcirc}-\underbrace{n\{(A\cup{B})\cap{C}\}}_{\diamondsuit}+n(C)\\ =&\underbrace{n(A)+n(B)-n(A\cap{B})}_{\bigcirc}\\ &-\underbrace{n\{(A\cap{C})\cup(B\cap{C})\}}_{\diamondsuit}+n(C)\\ &\blacktriangle~\bigcircの部分は『包含と排除の原理\\ &\quad（2集合版）』を、\diamondsuitの部分は\\ &\quad『要素の個数の基本 \text{ii}』を使った\\ =&n(A)+n(B)-n(A\cap{B})\\ &-\underbrace{n(A\cap{C})-n(B\cap{C})}_{\diamondsuit}\\ &\underbrace{+n\{(A\cap{C})\cap(B\cap{C})\}}_{\diamondsuit}+n(C)\\ &\blacktriangle~さらに\diamondsuitに\\ &\quad『包含と排除の原理（2集合版）』を使った\\ =&n(A)+n(B)+n(C)\\ &-n(A\cap{B})-n(B\cap{C})-n(C\cap{A})\\ &+n\{(A\cap{C})\cap(B\cap{C})\}\\ =&n(A)+n(B)+n(C)\\ &-n(A\cap{B})-n(B\cap{C})-n(C\cap{A})\\ &+n\{(A\cap(C\cap{B}\cap{C})\}\\ &\blacktriangle~B\cap{C}を1かたまりとして、\\ &\quad要素の個数の基本を使った\\ =&n(A)+n(B)+n(C)\\ &-n(A\cap{B})-n(B\cap{C})-n(C\cap{A})\\ &+n(A\cap{B}\cap{C})\\ &\blacktriangle~C\cap{C}=C~『共通部分』 \end{align}

包含と排除の原理（3集合版）

3つの集合$A$、$B$、$C$ に関して \begin{align} &n(A\cup{B}\cup{C})\\ =&n(A)+n(B)+n(C)\\ &\quad-n(A\cap{B})-n(B\cap{C})\\ &\quad-n(C\cap{A})+n(A\cap{B}\cap{C}) \end{align} が成り立つ。

吹き出し和集合の要素の個数（包含と排除の原理）

包含と排除の原理（3集合版）の図

包含と排除の原理（3集合版）の図

3集合の場合の包含と排除の原理も、包含と排除の原理（2集合版）の場合と似ている。$n(A\cup{B}\cup{C})$ を数えるのに、これを包み込む $n(A)+n(B)+n(C)$ をまず計算する。すると、重なっている部分ができてしまうので、$n(A\cap{B})+n(B\cap{C})+n(C\cap{A})$ を引くことにより除外する。しかし、これでは3つの集合が重なった部分を引きすぎてしまうので、最後に $n(A\cap{B}\cap{C})$ を加えておく。図で確認してみよう。