互いに素な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*}という関係が成り立つ。
例（包除原理）
\(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\)個の集合\(A_{1},A_{2},\cdots ,A_{n}\)がいずれも有限集合であるならば、和集合\(A_{1}\cup A_{2}\cup \cdots \cup A_{n}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cup A_{2}\cup \cdots \cup A_{n}\right\vert &=&\left\vert
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*}という関係が成り立つ。
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\)に具体的な数を入れてみます。
例（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 &=&\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*}という関係が成り立ちます。
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 &=&\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*}という関係が成り立ちます。
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\)個の集合の共通部分の濃度を引けばよいということです。
例（包除原理）
\(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\)個です。
演習問題
問題（包除原理）
期末試験を実施したところ、全受験者の\(80\)パーセントは国語の試験に合格し、全受験者の\(85\)パーセントが数学の試験に合格しました。また、\(75\)パーセントが国語と数学の両方の試験に合格しました。加えて、国語と数学の両方の試験で不合格であった受験者の数が\(45\)人でした。全受験者の人数を求めてください。
問題（包除原理）
ある会社には\(1000\)人の社員がおり、それぞれの社員は日本語・英語・中国語の中の少なくとも1つを話すことができるものとします。以下の条件が与えられているとき、三か国語をすべて話すことができる社員の人数を明らかにしてください。
- 日本語を話せるのは\(310\)人
- 英語を話せるのは\(650\)人
- 中国語を話せるのは\(440\)人
- 日本語を英語の両方を話せるのは\(170\)人
- 日本語と中国語の両方を話せるのは\(150\)人
- 英語と中国語の両方を話せるのは\(180\)人
プレミアム会員専用コンテンツです
【ログイン】【会員登録】