2014/03/11

包除原理の2通りの証明

分野: 場合の数  レベル: 最難関大学

包除原理:
$|A\cup B|=|A|+|B|-|A\cap B|$
$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$
$|A_1\cup A_2\cup\cdots\cup A_n|=\displaystyle\sum_{k=1}^n(-1)^{k-1}$ ($k$ 個の「かつ」の総和)
$=\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|-\cdots +(-1)^{n-1}|A_1\cap\cdots\cap A_n|$

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

この記事では包除原理の証明を2通りの方法で行います。
証明1、意味を考えつつ二項定理を用いる方法
証明2、数学的帰納法を用いてゴリゴリ計算していく方法

証明2は計算力さえあれば発想力はいらないというメリットがありますが,意味が分かりにくいです。そこで,証明1を通じて包除原理の本質的な意味を説明していきます。

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

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

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

具体的に $n=2$ の場合を見てみます。
AまたはB」が扱いにくいので,扱いやすい「A」や,「AかつB」を用いてどう表されるか考えます。

包除原理のイメージ

対称性から,うまくいくとしたら,$|A\cup B|=p_1|A|+p_1|B|+p_2|A\cap B|$ と表されることは分かるので,ベン図を見ながら $p_1, p_2$ を求めます。
図の1の部分が右辺でも1回カウントされる:$p_1=1$
図の2の部分については:$2p_1+p_2=1$
よって,$p_1=1, p_2=-1$ が分かります。

次に,$n=3$ の場合です。
AまたはBまたはC」が扱いにくいので,扱いやすい「A」や,「AかつB」,「AかつBかつC」を用いてどう表されるか考えます。
対称性から,$|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

と表されることは分かるので,ベン図を見ながら $p_1, p_2, p_3$ を求めます。
図の1の部分が右辺でも1回カウントされる:$p_1=1$
2の部分については:$_{2}C_1p_1+p_2=1$
3の部分については:$_{3}C_1p_1+_{3}C_2p_2+p_3=1$
よって,$p_1=1, p_2=-1, p_3=1$ が分かります。

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

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

方針:先ほどの議論の順番を工夫してスマートに証明します。(頭の中で定理の成り立ちを考える議論の流れと実際の証明の議論の流れは逆転することが多いです。)

証明1

包除原理の右辺で集合 $m$ 個の共通部分が何回現れているかを数え,それがどんな $m$ に対しても1に等しいことを示す。
右辺第一項で $m$ 回足され,第二項で$_{m}C_2$ 回引かれ,第3項で$_{m}C_3$ 回足され、 $\cdots$ なので,
数えたい回数は,$\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}C_k$
一方二項定理より,
$0=(1-1)^m=\displaystyle\sum_{k=0}^m {}_m{C}_k(-1)^k=1-\sum_{k=1}^m{}_m{C}_k(-1)^{k-1}$
よって,$\displaystyle\sum_{k=1}^{m}(-1)^{k-1}{}_{m}C_k=1$ となり題意は示された。

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

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

証明2

$n=2$ の場合は教科書に載っているので省略、帰納法で示す。
$|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|$

第一項と第三項を帰納法の仮定を用いて計算:
第一項$=\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)^{1-1}|A_n|\\$

第三項$=-|(A_1\cap A_n)\cup(A_2\cap A_n)\cup\cdots\cup(A_{n-1}\cap A_n)|\\
=-\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つの項を加える事により,包除原理が証明される:
$|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)$

なお,包除原理の応用としては例えば攪乱順列の公式全射の個数の証明とベル数があります。

数式がごちゃごちゃしていて大変ですが,しっかり理解して集合の記号に慣れましょう。

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

分野: 場合の数  レベル: 最難関大学