sataniC++

C++、競プロ、数学などについて色々考えたりします。

包除原理

目標

ある複数の集合における和集合の要素の個数を共通部分に配慮して正しく計算する。


説明

以下、有限集合A,B,C,\cdotsは全て全体集合Uの中に真に含まれているもの、|A|Aの濃度(元の個数)とします。

2つの集合について

集合A,Bについて、「AまたはBA\cup B)」であるものの集合の元の個数を求めてみましょう。
A\cup Bは、以下の図の赤い部分です。
f:id:satanic0258:20160410062119p:plain


まずは、「AまたはB」ということで単純に「Aの元の個数とBの元の個数の和」を見てみます(見やすさのために色を変えています)。
f:id:satanic0258:20160410070646p:plain

この図を見ると、以下の式が成り立っていることが分かりますね。
|A|+|B|=|A\cup B|+|A\cap B|

よって、以上の式を変形することで次のようにA\cup Bの元の個数を求めることが出来ました。
|A\cup B|=|A|+|B|-|A\cap B|


3つの集合について

次は、集合A,B,Cについて、「A\cup B\cup Cの元の個数」を求めてみましょう。

2つの集合のときと同様に、|A|+|B|+|C|を見てみます。
f:id:satanic0258:20160410080716p:plain


ここで、「AでありBであるがCではない」などの集合が最後に出てきていますが、こういった「○○でない」という集合(補集合と言います)は少し扱いにくいため、次のようなことをします。
f:id:satanic0258:20160410081326p:plain

こうすることで、補集合を用いずに以下の式が成り立つことが分かります。
|A|+|B|+|C|=|A\cup B\cup C|+|A\cap B|+|B\cap C|+|C\cap A|-|A\cap B\cap C|

よって、以上の式を変形することで次のように|A\cup B\cup C|を求めることが出来ました。
\displaystyle \begin{align}
 |A\cup B\cup C| &= |A|+|B|+|C|-(|A\cap B|+|B\cap C|+|C\cap A|-|A\cap B\cap C|)\\
&= |A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|
\end{align}


一般的な複数の集合について

ここでは詳しく触れませんが、n個の集合A_1,A_2,\cdotsにおける和集合\displaystyle \bigcup_i A_iの元の個数は、次のように表されます。

\displaystyle |\bigcup_i A_i|
\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 A_n|


具体例

20以下の自然数のうち「3の倍数または5の倍数」であるものの個数を求める

今、全体集合U、集合A,Bを次のように定義します。
U:=\{20以下の自然数\}
A:=\{3の倍数\}=\{3,6,9,12,15,18\}
B:=\{5の倍数\}=\{5,10,15,20\}

また、このとき次のことがわかります。
A\cup B=\{3の倍数または5の倍数\}
A\cap B=\{3の倍数かつ5の倍数\}=\{15の倍数\}=\{15\}


よって、先ほどの式に代入すると、
\begin{align}
 |A\cup B|&=|A|+|B|-|A\cap B|\\
&=6+4-1\\
&=9
\end{align}

ゆえに、20以下の自然数のうち「3の倍数または5の倍数」であるものは9個あることがわかりました。

f:id:satanic0258:20160410100739p:plain


あとがき

今回は、図で説明したほうがわかりやすいと思ったので、図を多めにしてみました。
なお、上記ではA\cap B=\emptysetである場合については触れていませんが、同様に計算することが出来ます。
あらゆる場面において同じ式が適応出来るので、ひとたび上記の式を覚えることでどんな集合の個数に関する計算でも出来てしまいますね。

ちなみに、4つ以上の集合に関するベン図を書こうとしたとき、全て真円で書くことが出来ないことが証明されているらしいです。
別の方法として、4つの楕円を重ねる方法や、3つの真円に1つの湾曲した楕円を上手く重ねる方法などがあるらしいですが、実用的ではないようです。