数学的なアレ。

レベルは低いですが数学について色々なことを書いていきます！

包除原理について少し解説

集合数学A

包除原理とは、以下のことを指します。

2つの集合 $A,B$ に対し
$n(A\cup B)=n(A)+n(B)-n(A\cap B)$

ここで、 $n(A)$ は集合 $A$ の要素数を表します。

包除原理は、「または」という状況を「かつ」という状況に変換できる公式です(逆も同様)。この公式は数学Aで初めて出てきますね。教科書によっては、「和集合の要素の個数の公式」というようなニュアンスの名前が付いているかもしれません。

なお、包除原理はさらに集合の個数を増やして一般化できるらしいのですが、正直よくわかっていないのでここでは省略します。

包除原理の証明についてはここでは詳しくはしませんが、集合が2,3個ほどの場合はベン図を用いて考えることができます(一般の場合にも同様の議論で可能なようです)。

やり方としては、集合(の要素数)やその共通部分などを足したり引いたりして左辺の状態にうまいこと持っていくような方法です。

数学的帰納法でも証明できるらしいですが、よく分かりません；

ここではとりあえず例題を解いてみます。

$($ 問 $).$ 集合 $A$ を $40$ 以下の $5$ の倍数の集合、集合 $B$ を $40$ 以下の $7$ の倍数の集合とするとき、 $n(A\cup B)$ を求めよ。

普通に求めにいってもいいのですが、ここでは包除原理を用いて解きます。

まず、 $A={5,10,15,20,25,30,35,40},B={7,14,21,28,35}$ より、

$n(A)=8,n(B)=5$

次に、 $A\cap B={35}$ より、

$n(A\cap B)=1$

これらを包除原理の式に当てはめると

$n(A)+n(B)-n(A\cap B)$

$=8+5-1$

$=12$

となります。

ちなみに左辺を普通に求めると、

$A\cup B={5,7,10,14,15,20,21,25,28,30,35,40}$ より、

$n(A\cup B)=12$

となり先ほどの結果と一致します。

物足りない感はありますが、今回はこの辺で。