1. 高校数学の美しい物語
  2. 包除原理の2通りの証明

包除原理の2通りの証明

更新日時 2021/03/07
包除原理

A1A2An|A_1\cup A_2\cup\cdots\cup A_n|

=iAii<jAiAj+i<j<kAiAjAk=\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cap A_j|+\sum_{i < j < k}|A_i\cap A_j\cap A_k| +(1)n1A1An\:\:\:-\cdots +(-1)^{n-1}|A_1\cap\cdots\cap A_n|

見た目がごついですが,とてもおもしろい公式です。包除原理の意味・証明・応用例を紹介します。

目次
  • 包除原理の意味

  • 包除原理を自分で作る

  • 包除原理の証明1:二項定理による方法

  • 包除原理の証明2:数学的帰納法による方法

  • 包除原理の応用

  • 「または」と「かつ」を交換した包除原理

包除原理の意味

  • 包除原理は,集合の要素数に関する等式です。
  • n=2n=2 の場合はおなじみの式になります:
    AB=A+BAB|A\cup B|=|A|+|B|-|A\cap B|
  • n=3n=3 の場合もおなじみです:
    ABC=A+B+CABBCCA+ABC|A\cup B\cup C|\\ =|A|+|B|+|C|\\ -|A\cap B|-|B\cap C|-|C\cap A|\\ +|A\cap B\cap C|
  • 包除原理の左辺は,nn 個の集合の「または」の要素数です。右辺は「かつ」の要素数です。「または」を「かつ」に変換する公式と言えます。場合の数や確率の問題では,「AまたはB」という条件は「AかつB」よりも扱いにくいことが多いです。そのような場合に包除原理を用いて「または」を「かつ」に変換できます。
  • 右辺を日本語で書くとわかりやすいです:
    A1A2An|A_1\cup A_2\cup\cdots\cup A_n|
    =k=1n(1)k1=\displaystyle\sum_{k=1}^n(-1)^{k-1}kk個の「かつ」の総和)

包除原理を自分で作る

「または」を「かつ」に変換する包除原理を自分で作ってみましょう。

n=2 の場合

AA またはBB」が扱いにくいので,扱いやすい「AA」や「AA かつ BB」を用いてどう表されるか考えます。

包除原理のイメージ

対称性から,うまくいくとしたら,AB=p1A+p1B+p2AB|A\cup B|=p_1|A|+p_1|B|+p_2|A\cap B| と表されることがわかります。

ベン図を見ながら p1,p2p_1, p_2 を求めます。

  • 図の1の部分が右辺でも1回カウントされる: p1=1p_1=1
  • 図の2の部分については: 2p1+p2=12p_1+p_2=1

よって,p1=1,p2=1p_1=1, p_2=-1 が分かります。

次に,n=3n=3 の場合です。

n=3 の場合

AA または BB または CC」が扱いにくいので,扱いやすい「AA」や「AA かつ BB」や「AA かつ BB かつ CC を用いてどう表されるか考えます。

対称性から,

ABC=p1A+p1B+p1C+p2AB+p2BC+p2CA+p3ABC|A\cup B\cup C|\\ =p_1|A|+p_1|B|+p_1|C|\\ +p_2|A\cap B|+p_2|B\cap C|+p_2|C\cap A|\\ +p_3|A\cap B\cap C|

包除原理のイメージ2

と表されることは分かるので,ベン図を見ながら p1,p2,p3p_1, p_2, p_3 を求めます。

  • 図の1の部分が右辺でも1回カウントされる: p1=1p_1=1
  • 2の部分については:2C1p1+p2=1_{2}\mathrm{C}_1p_1+p_2=1
  • 3の部分については: 3C1p1+3C2p2+p3=1_{3}\mathrm{C}_1p_1+_{3}\mathrm{C}_2p_2+p_3=1

よって,p1=1,p2=1,p3=1p_1=1, p_2=-1, p_3=1 が分かります。

同じ流れで一般の nn について包除原理を導くことが出来ます。

包除原理の証明1:二項定理による方法

方針

さきほどの議論の順番を工夫してスマートに証明します。包除原理の右辺で「集合ちょうど mm 個の共通部分」が何回現れているかを数え,それがどんな mm に対しても1に等しいことを示します。

証明1

右辺第一項で mm 回足され,第二項で mC2_{m}\mathrm{C}_2 回引かれ,第3項で mC3_{m}\mathrm{C}_3 回足され,\cdots なので,

数えたい回数は,k=1m(1)k1mCk\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}\mathrm{C}_k

一方,二項定理より,

0=(11)m=k=0mmCk(1)k=1k=1mmCk(1)k10=(1-1)^m\\ =\displaystyle\sum_{k=0}^m {}_m\mathrm{C}_k(-1)^k\\ =1-\displaystyle\sum_{k=1}^m{}_m\mathrm{C}_k(-1)^{k-1}

よって,k=1m(1)k1mCk=1\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}\mathrm{C}_k=1 となり題意は示された。

包除原理の証明2:数学的帰納法による方法

方針

集合の数が n1n-1 個の場合に包除原理が成立すると仮定して nn 個の場合にも成立することを示します。n=2n=2 の場合の包除原理を使って帰納法の仮定が使えるように変形して3つの項をそれぞれ計算します。

証明2

n=2n=2 の場合は簡単なので省略,帰納法で示す。

A1A2An=(A1A2An1)An=A1A2An1+An(A1A2An1)An|A_1\cup A_2\cup\cdots\cup A_n|\\ =|(A_1\cup A_2\cup\cdots\cup A_{n-1})\cup A_n|\\ =|A_1\cup A_2\cup\cdots\cup A_{n-1}|+|A_n|\\ \:-|(A_1\cup A_2\cup\cdots\cup A_{n-1}) \cap A_n|

第一項と第三項を帰納法の仮定を用いて計算:

第一項 =k=1n1((1)k1i1ikAi1Aik)=\displaystyle\sum_{k=1}^{n-1}\left((-1)^{k-1}\sum_{i_1 \cdots i_k}|A_{i_1}\cap\cdots\cap A_{i_k}|\right)

第二項 =(1)11An=(-1)^{1-1}|A_n|

第三項 =(A1An)(A2An)(An1An)=(1)×k=1n1((1)k1i1ik(Ai1An)(AikAn))=k=1n1((1)ki1ik(Ai1Aik)An)=-|(A_1\cap A_n)\cup(A_2\cap A_n)\cup\cdots\cup(A_{n-1}\cap A_n)|\\ =(-1)\times\\ \displaystyle\sum_{k=1}^{n-1}\left((-1)^{k-1}\sum_{i_1 \cdots i_k}|(A_{i_1}\cap A_n)\cap \cdots\cap (A_{i_k}\cap A_n)|\right)\\ =\displaystyle\sum_{k=1}^{n-1}\left((-1)^{k}\sum_{i_1 \cdots i_k}|(A_{i_1}\cap\cdots\cap A_{i_k})\cap A_n|\right)

包除原理の証明

3つの項を加える事により,包除原理が証明される:

A1A2An=k=1n((1)k1i1ikAi1Aik)|A_1\cup A_2\cup\cdots\cup A_n|\\=\displaystyle\sum_{k=1}^{n}\left((-1)^{k-1}\sum_{i_1 \cdots i_k}|A_{i_1}\cap\cdots\cap A_{i_k}|\right)

「または」と「かつ」を交換した包除原理

実は「または」と「かつ」を交換した包除原理も成立します:

AB=A+BAB|A\cap B|=|A|+|B|-|A\cup B|

ABC=A+B+CABBCCA+ABC|A\cap B\cap C|\\ =|A|+|B|+|C|\\ -|A\cup B|-|B\cup C|-|C\cup A|\\ +|A\cup B\cup C|

より一般に,

A1A2An=iAii<jAiAj+i<j<kAiAjAk+(1)n1A1An|A_1\cap A_2\cap\cdots\cap A_n|\\ =\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cup A_j| +\sum_{i < j < k}|A_i\cup A_j\cup A_k|\\ -\cdots +(-1)^{n-1}|A_1\cup\cdots\cup A_n|

証明

一般の場合も同様なので,集合が3つの場合について証明する。全体集合を

U=ABCU=A\cup B\cup C として,それぞれの補集合に「普通の包除原理」を適用する:

ABC=A+B+CABBCCA+ABC|\overline{A}\cup \overline{B}\cup \overline{C}|\\ =|\overline{A}|+|\overline{B}|+|\overline{C}|\\ -|\overline{A}\cap \overline{B}|-|\overline{B}\cap \overline{C}|-|\overline{C}\cap \overline{A}|\\ +|\overline{A}\cap \overline{B}\cap \overline{C}|

ド・モルガンの法則を使うと「または」と「かつ」がひっくり返る:

ABC=A+B+CABBCCA+ABC|\overline{A\cap B\cap C}|\\ =|\overline{A}|+|\overline{B}|+|\overline{C}|\\ -|\overline{A\cup B}|-|\overline{B\cup C}|-|\overline{C\cup A}|\\ +|\overline{A\cup B\cup C}|

最後にそれぞれの項について,補集合の要素数公式 S=US|\overline{S}|=|U|-|S| を使うと,求める公式になる。

「または」と「かつ」を交換した包除原理は,読者の方に教えていただくまで知りませんでした!

Tag:数学的帰納法のパターンまとめ

人気記事
  1. 高校数学の美しい物語
  2. 包除原理の2通りの証明