互いに素な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*}が成り立ちます。つまり、互いに素な有限集合どうしの和集合の濃度は、個々の集合の濃度の和に等しいということです。
命題（互いに素な2つの有限集合の和集合の濃度）
集合\(A,B\)がともに有限集合であるとともに互いに素であるならば、和集合\(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）と呼びます。
命題（2つの有限集合の和集合の濃度）
集合\(A,B\)がともに有限集合であるならば、和集合\(A\cup B\)もまた有限集合であるとともに、\begin{equation*}\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}が成り立つ。
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}が成り立つ。
例（共通部分を引く理由）
以下の集合\begin{eqnarray*}
A &=&\left\{ 1,2,3,4\right\} \\
B &=&\left\{ 3,4,5\right\}
\end{eqnarray*}について、\begin{eqnarray*}
\left\vert A\right\vert &=&4 \\
\left\vert B\right\vert &=&3
\end{eqnarray*}が成り立ちますが、\begin{equation*}
\left\vert A\right\vert +\left\vert B\right\vert =7
\end{equation*}では\(3\)と\(4\)を2回ずつ数えています。\begin{equation*}A\cap B=\left\{ 3,4\right\}
\end{equation*}ゆえに、\begin{equation*}
\left\vert A\cap B\right\vert =2
\end{equation*}であるため、\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 \\
&=&4+3-2 \\
&=&5
\end{eqnarray*}です。実際、\begin{equation*}
A\cup B=\left\{ 1,2,3,4,5\right\}
\end{equation*}であるため、\begin{equation*}
\left\vert A\cup B\right\vert =5
\end{equation*}です。
A &=&\left\{ 1,2,3,4\right\} \\
B &=&\left\{ 3,4,5\right\}
\end{eqnarray*}について、\begin{eqnarray*}
\left\vert A\right\vert &=&4 \\
\left\vert B\right\vert &=&3
\end{eqnarray*}が成り立ちますが、\begin{equation*}
\left\vert A\right\vert +\left\vert B\right\vert =7
\end{equation*}では\(3\)と\(4\)を2回ずつ数えています。\begin{equation*}A\cap B=\left\{ 3,4\right\}
\end{equation*}ゆえに、\begin{equation*}
\left\vert A\cap B\right\vert =2
\end{equation*}であるため、\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 \\
&=&4+3-2 \\
&=&5
\end{eqnarray*}です。実際、\begin{equation*}
A\cup B=\left\{ 1,2,3,4,5\right\}
\end{equation*}であるため、\begin{equation*}
\left\vert A\cup B\right\vert =5
\end{equation*}です。
例（一方が他方の部分集合である場合）
有限集合\(A,B\)について、\begin{equation*}A\subset B
\end{equation*}が成り立つものとします。このとき、\begin{eqnarray*}
A\cup B &=&B \\
A\cap B &=&A
\end{eqnarray*}が成り立つため、包除原理\begin{equation*}
\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}は、\begin{equation*}
\left\vert B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert
-\left\vert A\right\vert
\end{equation*}となりますが、これは明らかに成り立ちます。この例は、2つの集合の間に包含関係が成立する場合にも包除原理が正しく機能することを示します。
\end{equation*}が成り立つものとします。このとき、\begin{eqnarray*}
A\cup B &=&B \\
A\cap B &=&A
\end{eqnarray*}が成り立つため、包除原理\begin{equation*}
\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}は、\begin{equation*}
\left\vert B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert
-\left\vert A\right\vert
\end{equation*}となりますが、これは明らかに成り立ちます。この例は、2つの集合の間に包含関係が成立する場合にも包除原理が正しく機能することを示します。
例（互いに素な場合）
有限集合\(A,B\)について、\begin{equation*}A\cap B=\phi
\end{equation*}が成り立つものとします。この場合、\begin{equation*}
\left\vert A\cap B\right\vert =\left\vert \phi \right\vert =0
\end{equation*}であるため、包除原理\begin{equation*}
\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}は、\begin{equation*}
\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert
\end{equation*}となります。これは互いに素な2つの有限集合の和集合の濃度に関する公式に他なりません。以上の例は、包除原理が2つの集合が互いに素な場合の一般化であることを示します。
\end{equation*}が成り立つものとします。この場合、\begin{equation*}
\left\vert A\cap B\right\vert =\left\vert \phi \right\vert =0
\end{equation*}であるため、包除原理\begin{equation*}
\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}は、\begin{equation*}
\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert
\end{equation*}となります。これは互いに素な2つの有限集合の和集合の濃度に関する公式に他なりません。以上の例は、包除原理が2つの集合が互いに素な場合の一般化であることを示します。
例（包除原理）
\(1\)以上\(100\)以下の整数の中に\(2\)もしくは\(3\)の倍数はいくつ存在するでしょうか。\(1\)以上\(100\)以下の整数の中でも\(2\)で割れるものの集合を\(A\)で表記するのであれば、\begin{equation}\left\vert A\right\vert =50 \quad \cdots (1)
\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\)個です。
\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\)に関する数学的帰納法を利用します。
命題（有限個の有限集合の和集合の濃度）
自然数\(n\in \mathbb{N} \)について、有限\(n\)個の集合\(A_{1},\cdots ,A_{n}\)がいずれも有限集合であるならば、和集合\begin{equation*}\bigcup\limits_{i=1}^{n}A_{i}
\end{equation*}もまた有限集合であるとともに、\begin{equation*}
\left\vert \bigcup\limits_{i=1}^{n}A_{i}\right\vert =\sum_{\phi
\not=I\subset \left\{ 1,\cdots ,n\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert
\end{equation*}が成り立つ。
\end{equation*}もまた有限集合であるとともに、\begin{equation*}
\left\vert \bigcup\limits_{i=1}^{n}A_{i}\right\vert =\sum_{\phi
\not=I\subset \left\{ 1,\cdots ,n\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert
\end{equation*}が成り立つ。
例（3個の有限集合の和集合の濃度）
\(3\)個の集合\(A_{1},A_{2},A_{3}\)がいずれも有限集合であるならば、先の命題より和集合\(A_{1}\cup A_{2}\cup A_{3}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert &=&\sum_{\phi \not=I\subset
\left\{ 1,2,3\right\} }\left( -1\right) ^{\left\vert I\right\vert
+1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&\left\vert 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*}が成り立ちます。
\left\{ 1,2,3\right\} }\left( -1\right) ^{\left\vert I\right\vert
+1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&\left\vert 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*}が成り立ちます。
例（4個の有限集合の和集合の濃度）
\(4\)個の集合\(A_{1},A_{2},A_{3},A_{4}\)がいずれも有限集合であるならば、先の命題より和集合\(A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\right\vert &=&\sum_{\phi
\not=I\subset \left\{ 1,2,3,4\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&\left\vert 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*}が成り立ちます。
\not=I\subset \left\{ 1,2,3,4\right\} }\left( -1\right) ^{\left\vert
I\right\vert +1}\left\vert \bigcap\limits_{i\in I}A_{i}\right\vert \\
&=&\left\vert 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},\cdots ,A_{n}\)の和集合の濃度を求めるためには、まず、\(n\)個の集合の濃度を足し、次に、\(n\)個の集合から\(2\)個を選んでできる共通部分（このような共通部分は\(\binom{n}{2}\)通り存在する）の濃度の総和を引き、次に、\(n\)個の集合から\(3\)個を選んでできる共通部分（このような共通部分は\(\binom{n}{3}\)通り存在する）の濃度の総和を足し、次に、\(n\)個の集合から\(4\)個を選んでできる共通部分（このような共通部分は\(\binom{n}{4}\)通り存在する）の濃度の総和を引き、\(\cdots \)という作業を続け、最終的に、\(n\)が奇数ならば\(n\)個の集合の共通部分の濃度を足し、\(n\)が偶数ならば\(n\)個の集合の共通部分の濃度を引けばよいということです。
例（包除原理）
\(1\)以上かつ\(60\)以下の整数の中に\(3\)または\(4\)または\(5\)の中の少なくとも1つで割り切れる数はいくつ存在するでしょうか。\(1\)以上\(60\)以下の整数の中で\(3\)で割れるものからなる集合を\(A\)で表記するのであれば、\begin{equation*}\left\vert A\right\vert =20
\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\)個です。
\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\)個です。
演習問題
問題（包除原理）
有限集合\(A,B\)について、\begin{eqnarray*}\left\vert A\right\vert &=&28 \\
\left\vert B\right\vert &=&35 \\
\left\vert A\cup B\right\vert &=&50
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cap B\right\vert
\end{equation*}を求めてください。
\left\vert B\right\vert &=&35 \\
\left\vert A\cup B\right\vert &=&50
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cap B\right\vert
\end{equation*}を求めてください。
問題（包除原理）
期末試験を実施したところ、全受験者の\(80\)パーセントは国語の試験に合格し、全受験者の\(85\)パーセントが数学の試験に合格しました。また、\(75\)パーセントが国語と数学の両方の試験に合格しました。加えて、国語と数学の両方の試験で不合格であった受験者の数が\(40\)人でした。全受験者の人数、国語の合格者数、数学の合格者数、国語と数学双方の合格者数をそれぞれ求めてください。
問題（和集合の濃度の上限と下限）
有限集合\(A,B\)について、\begin{equation*}\max \left\{ \left\vert A\right\vert ,\left\vert B\right\vert \right\} \leq
\left\vert A\cup B\right\vert \leq \left\vert A\right\vert +\left\vert
B\right\vert
\end{equation*}が成り立つことを証明してください。
\left\vert A\cup B\right\vert \leq \left\vert A\right\vert +\left\vert
B\right\vert
\end{equation*}が成り立つことを証明してください。
問題（和集合の濃度の範囲）
有限集合\(A,B\)について、\begin{eqnarray*}\left\vert A\right\vert &=&20 \\
\left\vert B\right\vert &=&15
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cup B\right\vert
\end{equation*}がとり得る最小値と最大値を求めてください。
\left\vert B\right\vert &=&15
\end{eqnarray*}が成り立つものとします。\begin{equation*}
\left\vert A\cup B\right\vert
\end{equation*}がとり得る最小値と最大値を求めてください。
問題（包除原理）
ある会社には\(1000\)人の社員がおり、それぞれの社員は日本語・英語・中国語の中の少なくとも1つを話すことができるものとします。以下の条件が与えられているとき、三か国語をすべて話すことができる社員の人数を明らかにしてください。
- 日本語を話せるのは\(310\)人
- 英語を話せるのは\(650\)人
- 中国語を話せるのは\(440\)人
- 日本語と英語の両方を話せるのは\(170\)人
- 日本語と中国語の両方を話せるのは\(150\)人
- 英語と中国語の両方を話せるのは\(180\)人
問題（互いに素な有限集合族）
有限\(n\)個の有限集合\(A_{1},\cdots ,A_{n}\)の中からどの2つを選んでも互いに素である場合には、\begin{equation*}\left\vert \bigcup\limits_{i=1}^{n}A_{i}\right\vert
=\sum_{i=1}^{n}\left\vert A_{i}\right\vert
\end{equation*}が成り立つことを証明してください。
=\sum_{i=1}^{n}\left\vert A_{i}\right\vert
\end{equation*}が成り立つことを証明してください。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。