互いに素な2つの有限集合の和集合の濃度
2つの集合\(A,B\)がともに有限集合であるとともに互いに素である場合、すなわち、\begin{equation*}A\cap B=\phi
\end{equation*}が成り立つ場合、和集合\(A\cup B\)もまた有限集合になるとともに、これらの集合の濃度の間には、\begin{equation*}\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert
\end{equation*}という関係が成り立つことが保証されます。つまり、互いに素な有限集合どうしの和集合の濃度は、個々の集合の濃度の和に等しいということです。
B\right\vert
\end{equation*}という関係が成り立つ。
2つの有限集合の和集合の濃度(包除原理)
2つの有限集合\(A,B\)が互いに素であるとは限らない場合、和集合\(A\cup B\)の濃度についてどのようなことが言えるでしょうか。互いに素であるとは限らない集合\(A,B\)の和集合に関して以下の集合変形\begin{equation*}A\cup B=\left( A\backslash B\right) \cup \left( B\backslash A\right) \cup
\left( A\cap B\right)
\end{equation*}が可能であることと先の命題を踏まえると以下を得ます。これを包除原理(inclusion-exclusion principle)と呼びます。
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}という関係が成り立つ。
\end{equation}が成り立ちます。また、\(1\)以上\(100\)以下の整数の中でも\(3\)で割れるものからなる集合を\(B\)で表記するのであれば、\begin{equation}\left\vert B\right\vert =33 \quad \cdots (2)
\end{equation}が成り立ちます。\(1\)以上\(100\)以下の整数の中でも\(2\)と\(3\)で割り切れるもの、すなわち\(6\)で割り切れるものからなる集合は\(A\cap B\)であり、\begin{equation}\left\vert A\cap B\right\vert =16 \quad \cdots (3)
\end{equation}となります。問題としているのは和集合\(A\cup B\)の濃度であるため、\begin{eqnarray*}\left\vert A\cup B\right\vert &=&\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert \quad \because \text{除法原理} \\
&=&50+33-16 \\
&=&67
\end{eqnarray*}となります。したがって答えは\(67\)個です。
有限個の有限集合の和集合の濃度(包除原理の一般化)
先の命題は3個以上の有限集合の和集合に関しても拡張可能です。証明では集合の個数\(n\)に関する数学的帰納法を利用します。
A_{1}\right\vert +\left\vert A_{2}\right\vert +\cdots +\left\vert
A_{n}\right\vert \\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\cdots -\left\vert A_{n-1}\cap A_{n}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert +\cdots +\left\vert
A_{n-2}\cap A_{n-1}\cap A_{n}\right\vert \\
&&\vdots \\
&&+\left( -1\right) ^{n-1}\left\vert A_{1}\cap A_{2}\cap \cdots \cap
A_{n}\right\vert
\end{eqnarray*}という関係が成り立つ。
このままでは分かりづらいため、上の命題中の\(n\)に具体的な数を入れてみます。
A_{1}\right\vert +\left\vert A_{2}\right\vert +\left\vert A_{3}\right\vert
\\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\left\vert A_{2}\cap A_{3}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert
\end{eqnarray*}という関係が成り立ちます。
A_{1}\right\vert +\left\vert A_{2}\right\vert +\left\vert A_{3}\right\vert
+\left\vert A_{4}\right\vert \\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\left\vert A_{1}\cap A_{4}\right\vert -\left\vert
A_{2}\cap A_{3}\right\vert -\left\vert A_{2}\cap A_{4}\right\vert
-\left\vert A_{3}\cap A_{4}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert +\left\vert A_{1}\cap
A_{2}\cap A_{4}\right\vert +\left\vert A_{1}\cap A_{3}\cap A_{4}\right\vert
+\left\vert A_{2}\cap A_{3}\cap A_{4}\right\vert \\
&&-\left\vert A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\right\vert
\end{eqnarray*}という関係が成り立ちます。
つまり、有限\(n\)個の集合\(A_{1},A_{2},\cdots ,A_{n}\)の和集合の濃度を求めるためには、まず、\(n\)個の集合の濃度を足し、次に、\(n\)個の集合から\(2\)個を選んでできる共通部分(このような共通部分は\(\binom{n}{2}\)通り存在する)の濃度の総和を引き、次に、\(n\)個の集合から\(3\)個を選んでできる共通部分(このような共通部分は\(\binom{n}{3}\)通り存在する)の濃度の総和を足し、次に、\(n\)個の集合から\(4\)個を選んでできる共通部分(このような共通部分は\(\binom{n}{4}\)通り存在する)の濃度の総和を引き、\(\cdots \)という作業を続け、最終的に、\(n\)が奇数ならば\(n\)個の集合の共通部分の濃度を足し、\(n\)が偶数ならば\(n\)個の集合の共通部分の濃度を引けばよいということです。
\end{equation*}が成り立ちます。また、\(1\)以上\(60\)以下の整数の中でも\(4\)で割れるものからなる集合を\(B\)で表記するのであれば、\begin{equation*}\left\vert B\right\vert =15
\end{equation*}が成り立ちます。さらに、\(1\)以上\(60\)以下の整数の中でも\(5\)で割れるものからなる集合を\(C\)で表記するのであれば、\begin{equation*}\left\vert C\right\vert =12
\end{equation*}が成り立ちます。\(1\)以上\(60\)以下の整数の中でも\(3\)と\(4\)で割り切れるもの、すなわち\(12\)で割り切れるものからなる集合は\(A\cap B\)であり、\begin{equation*}\left\vert A\cap B\right\vert =5
\end{equation*}となります。\(1\)以上\(60\)以下の整数の中でも\(3\)と\(5\)で割り切れるもの、すなわち\(15\)で割り切れるものからなる集合は\(A\cap C\)であり、\begin{equation*}\left\vert A\cap C\right\vert =4
\end{equation*}となります。\(1\)以上\(60\)以下の整数の中でも\(4\)と\(5\)で割り切れるもの、すなわち\(20\)で割り切れるものからなる集合は\(B\cap C\)であり、\begin{equation*}\left\vert B\cap C\right\vert =3
\end{equation*}となります。\(1\)以上\(60\)以下の整数の中でも\(3\)と\(4\)と\(5\)で割り切れるもの、すなわち\(60\)で割り切れるものからなる集合は\(A\cap B\cap C\)であり、\begin{equation*}\left\vert A\cap B\cap C\right\vert =1
\end{equation*}となります。問題としているのは和集合\(A\cup B\cup C\)の濃度ですが、\begin{eqnarray*}\left\vert A\cup B\cup C\right\vert &=&\left\vert A\right\vert +\left\vert
B\right\vert +\left\vert C\right\vert -\left\vert A\cap B\right\vert
-\left\vert A\cap C\right\vert -\left\vert B\cap C\right\vert +\left\vert
A\cap B\cap C\right\vert \quad \because \text{除法原理} \\
&=&20+15+12-5-4-3+1 \\
&=&36
\end{eqnarray*}となります。したがって答えは\(36\)個です。
演習問題
- 日本語を話せるのは\(310\)人
- 英語を話せるのは\(650\)人
- 中国語を話せるのは\(440\)人
- 日本語を英語の両方を話せるのは\(170\)人
- 日本語と中国語の両方を話せるのは\(150\)人
- 英語と中国語の両方を話せるのは\(180\)人
プレミアム会員専用コンテンツです
【ログイン】【会員登録】