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

包除原理の2通りの証明

更新日時 2021/03/07

包除原理:

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

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|

より一般に,

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

=k=1n(1)k1=\displaystyle\sum_{k=1}^n(-1)^{k-1}kk個の「かつ」の総和)

=iAii<jAiAj=\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cap A_j|

+i<j<kAiAjAk+\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|

上の2つの式は教科書でもおなじみの公式ですね。しかし,初めて包除原理を知った人にとっては最後の式は意味不明でしょう。

この記事では包除原理の意味と,2通りの証明を紹介します。

証明1.意味を考えつつ二項定理を用いる方法

証明2.数学的帰納法を用いてゴリゴリ計算していく方法

目次
  • 包除原理の意味と n=2,3n=2, 3 の場合の証明

  • 二項定理を用いた包除原理の証明

  • 数学的帰納法を用いた包除原理の証明

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

包除原理の意味と n=2,3n=2, 3 の場合の証明

大雑把にいえば, 包除原理は「または」を「かつ」に変換するための道具と言えます。この意味が理解できれば,ゴツイ数式にも抵抗がなくなると思います。

場合の数や確率の問題では, 「AまたはB」という条件は「AかつB」よりも扱いにくいことが多いです。そのような場合に包除原理を用いて「または」を「かつ」に変換してやります。

具体的に n=2n=2 の場合を見てみます。

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

包除原理のイメージ

対称性から,うまくいくとしたら,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 の場合です。

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

対称性から,

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に等しいことを示す。

右辺第一項で 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 となり題意は示された。

数学的帰納法を用いた包除原理の証明

方針:集合の数が 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通りの証明