WIIS

集合の濃度

有限集合の和集合の濃度(包除原理)

目次

関連知識

Mailで保存
Xで共有

互いに素な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*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

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*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(包除原理)
\(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\)個です。

 

有限個の有限集合の和集合の濃度(包除原理の一般化)

先の命題は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*}という関係が成り立つ。

このままでは分かりづらいため、上の命題中の\(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*}という関係が成り立ちます。

例(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*}という関係が成り立ちます。

つまり、有限\(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\)個です。

 

演習問題

問題(包除原理)
期末試験を実施したところ、全受験者の\(80\)パーセントは国語の試験に合格し、全受験者の\(85\)パーセントが数学の試験に合格しました。また、\(75\)パーセントが国語と数学の両方の試験に合格しました。加えて、国語と数学の両方の試験で不合格であった受験者の数が\(45\)人でした。全受験者の人数を求めてください。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(包除原理)
ある会社には\(1000\)人の社員がおり、それぞれの社員は日本語・英語・中国語の中の少なくとも1つを話すことができるものとします。以下の条件が与えられているとき、三か国語をすべて話すことができる社員の人数を明らかにしてください。

  1. 日本語を話せるのは\(310\)人
  2. 英語を話せるのは\(650\)人
  3. 中国語を話せるのは\(440\)人
  4. 日本語を英語の両方を話せるのは\(170\)人
  5. 日本語と中国語の両方を話せるのは\(150\)人
  6. 英語と中国語の両方を話せるのは\(180\)人
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録