集合の要素の個数と場合の数

“場合”を集合の要素に対応させる

球の並べ方

球の並べ方

ある事柄の起こり方が全部で $a$ 通りあるとき, その事柄の起こる場合の数(number of cases)は $a$ 通りであるという.

この事柄の起こり方は,集合の要素に対応させることができる.

例えば,①の球が3個,②の球が2個,計5個の球があるとする.

この中から3個選んで,順に1列に並べるという事柄をAとすると事柄Aには,右図のように7通りの場合がある.

これを順に $a_1,a_2,\cdots,a_7$ と対応させ集合 $A$ を作る. このとき,場合の数は $n(A)$ と表せる.

このように,事柄における“場合”は,集合の要素に簡単に対応させることができる. このように対応させることにより,場合の数を求める際,『集合の要素の個数』で学んだことが利用できる.

以下,特に断りのない限り,事柄Xと集合 $X$ は互いに対応しているものとし,どちらも斜体のアルファベット $X$ で表すことにする.

積の法則・和の法則(集合版)

積の法則・和の法則の利用

1,2,3,4,5,6の数字が書いてあるさいころを1回振り,さらに1,2,3,4の数字が書いてある4枚のカードから1枚引くとする.

  1. 2つの数字の出方には全部で何通りの場合があるか.
  2. 2つの数字の和が4の倍数となるのは何通りか.

  1. さいころの数字6通りのそれぞれに対して,カードの数字は4通りに定まるから,積の法則より \[6\times4=\boldsymbol{24}通り\]

    《補足》 このことを,集合で表現すると以下のようになる.

    $A$ :「さいころを1回振る」

    $B$ :「カードを1枚引く」

    とおくと,求める場合の数は $n(A\times{B})$ となり

    \begin{align} n(A\times{B})&= n(A)\times{n(B)}\\ &= 6\times4=\boldsymbol{24}通り \end{align}
  2. 2つの数字の和が4の倍数となるのは
    1. 2つの数字の和が4の場合
    2. 2つの数字の和が8の場合

    に分けることができ,i)の場合は(さいころ,カード)の順で $(1,~3),(2,~2),(3,~1)$ の3通りあり,

    ii)の場合も $(4,~4),(5,~3),(6,~2)$ の3通りある.

    また,これらは同時に起こることはないから,和の法則より

    \[3+3=\boldsymbol{6}通り\]

    《補足》 このことを,集合で表現すると以下のようになる.

    $P$ :「2つの数字の和が4である」

    $Q$ :「2つの数字の和が8である」

    とおくと,求める場合の数は $n(P\cup{Q})$ となり, $P\cap{Q}=\emptyset$ であるから \begin{align} n(P\cup{Q})&=n(P)+n(Q)\\ &=3+3=\boldsymbol{6}通り \end{align}

補集合での考え方

補集合の利用

1,2,3,4,5,6の数字が書いてあるさいころを1回振り,さらに1,2,3,4の数字が書いてある4枚のカードから1枚引くとする.

2つの数字の和が4の倍数とは"ならない"のは何通りか.

積の法則・和の法則の利用の例題(1)で求めた全体24通りのうち,「2つの数字の和が4の倍数となる」のは(2)より,6通りである.

よって,「2つの数字の和が4の倍数とは

ならない

」のは

$24-6=\boldsymbol{18}$ 通り.

《補足》 このことを,集合で表現すると以下のようになる.

全体集合 $U$ を $U=A\times{B}$ とおくと,求める場合の数は $n(\overline{P\cup{Q}})$ であるから

\begin{align} n(\overline{P\cup{Q}}) &= n(U)-n(P\cup{Q})\\ &= 24-6=\boldsymbol{18}通り \end{align}

この問題は,補集合の考え方を使わなくても,例えば和の法則で次のように解くこともできる.

$A_1$ :「カードの数字が1の場合で2つの数字の和が4の倍数になる」

$A_2$ :「カードの数字が2の場合で2つの数字の和が4の倍数になる」

$A_3$ :「カードの数字が3の場合で2つの数字の和が4の倍数になる」

$A_4$ :「カードの数字が4の場合で2つの数字の和が4の倍数になる」

とおくと,どの2つの事柄も同時におこることがないので

$5+4+4+5=\boldsymbol{18}$ 通り

となるが,補集合を考えたときに比べてかなり面倒である.

そこで,次のような原則を引き出すことができるだろう.

補集合で考えるときのポイント

全体集合 $U$ に対して, $n(X)$ を数えるよりも $n(\overline{X})$ を数えるほうが数えやすいとき

\[n(X)=n(U)-n(\overline{X})\]

として, $n(X)$ を計算するとよい.

ド・モルガンの法則

ド・モルガンの法則

1,2,3,4,5,6の数字が書いてあるさいころを1回振り,さらに1,2,3,4の数字が書いてある4枚のカードから1枚引くとする. 2つの数字の積が偶数となるのは何通りか.

2つの数字の偶奇とその積の偶奇の関係は下の表のようになる.

\begin{array}{|c|c|c|c|c|}\hline さいころ&&カード&&積\\\hline 奇数&×&奇数&=&奇数\\\hline 奇数&×&偶数&=&偶数\\\hline 偶数&×&奇数&=&偶数\\\hline 偶数&×&偶数&=&偶数\\\hline \end{array}

これより,積が偶数になる場合より,奇数になる場合の方が数えやすそうだとわかるので,補集合を考えてみることにする.

$C$ :「さいころの数字が偶数である」

D:「カードの数字が偶数である」

とおくと,求める場合の数は $n(C\cup{D})$ であり,その補集合の要素の個数は $n(\overline{C\cup{D}})$ であるから, 全体集合を $U$ とすると

\[n(C\cup{D})=n(U)-n(\overline{C\cup{D}})\]

ここで,『ド・モルガンの法則』より

\[n(\overline{C\cup{D}})=n(\overline{C}\cap\overline{D})\]

であり,集合 $\overline{C}\cap\overline{D}$ に対応する事柄は,「さいころの数字が偶数でなく,かつ,カードの数字が偶数でない」つまり

\[「さいころ,カードの数字がともに奇数である」\]

となるので,積の法則から

\[n(\overline{C}\cap\overline{D})=3\times2=6\]

よって

\begin{align} n(C\cup{D})&=n(U)-n(\overline{C\cup{D}})\\ &=n(U)-n(\overline{C}\cap\overline{D})\\ &=24-6=\boldsymbol{18} \end{align}

通り

吹き出しド・モルガンの法則を使うときには

  1. 形式的な面
  2. 意味的な面

の両方から,考える癖をつけるのがよい.

つまり,上の問題の例でいうならば,i)では

$\qquad$ 集合 $\overline{C\cup{D}}$ は,補集合のバー $(\overline{\bigcirc})$ が“切れて” $\cup$ が“ひっくりかえった”集合 $\overline{C}\cap\overline{D}$
$\qquad$ と常に等しかったな.そして,この $\overline{C}\cap\overline{D}$ は,「数字がともに奇数である」という事柄と対応するな.

と考えることであり,ii)では

$\qquad$ 「(さいころの数字が偶数であるか,または,カードの数字が偶数である)ということはない」,とはつまり,「さいころ,カードの数字がともに奇数であること」と同じだな.
$\qquad$ だから,それぞれに対応する集合 $\overline{C\cup{D}}$ と $\overline{C}\cap\overline{D}$ は等しくなるな.

と考えることである.

上の解答では,i)を強調した書き方になっている.

包含と排除の原理

2集合の包含と排除の原理

1,2,3,4,5,6の数字が書いてあるさいころを1回振り,さらに1,2,3,4の数字が書いてある4枚のカードから1枚引くとする. 2つの数字の積が偶数となるのは何通りか.『包含と排除の原理』を用いて求めよ.

『ド・モルガンの法則』の例題の場合と同じように

$C$ :「さいころの数字が偶数である」

$D$ :「カードの数字が偶数である」

とおくと,求める場合の数は $n(C\cup{D})$ である. 和集合の要素の個数に関して

\[n(C\cup{D})=n(C)+n(D)-n(C\cap{D})\]

が成り立つ.また,集合 $C\cap{D}$ に対応する事柄は

$\qquad$ 「さいころ,カードの数字が共に偶数」

となる.

ここで, $n(C)$ , $n(D)$ , $n(C\cap{D})$ はそれぞれ

\[n(C)=3\times4=12\] \[n(D)=6\times2=12\] \[n(C\cap{D})=3\times2=6\]

となるので

\begin{align} n(C\cup{D})&=n(C)+n(D)-n(C\cap{D})\\ &=12+12-6=\boldsymbol{18} \end{align}

通り

集合を利用した数え上げのまとめ

1から100までの自然数のうち,次のような数は全部でいくつあるか.

  1. 3で割りきれ,かつ,7で割りきれる数.
  2. 3で割りきれるか,または,7で割りきれる数.
  3. 3で割りきれなく,かつ,7で割りきれない数.
  4. 3で割りきれないか,または,7で割りきれない数.

事柄A,Bをそれぞれ

$\qquad A$ :「3で割りきれる」

$\qquad B$ :「7で割りきれる」

とする.まず, $n(A)$ と $n(B)$ について

$\qquad 100\div3=33$ あまり1

$\qquad 100\div7=14$ あまり2

であるから

$\qquad n(A) = 33,n(B) = 14$

である.

  1. 「3で割りきれ,かつ,7で割りきれる数」は集合で $A\cap{B}$ と表すことができ, これは結局「21で割りきれる数」のことである.
  2. $100\div21=4$ あまり16であるから

    $n(A\cap{B})=\boldsymbol{4}$

  3. 「3で割りきれるか,または,7で割りきれる数」は集合で $A\cup{B}$ と表すことができる.
  4. \begin{align} &n(A\cup{B})\\ =&n(A)+n(B)-n(A\cap{B})\\ =&33+14-4\\ =&33+14-4=\boldsymbol{43} \end{align}
  5. 求める場合の数は $n(\overline{A}\cap\overline{B})$ である.全体集合をUとすると
  6. \begin{align} &n(\overline{A}\cap\overline{B})\\ =&n(\overline{A\cup{B}})\\ =&n(U)-n(A\cup{B})\\ =&100-43=\boldsymbol{57} \end{align}
  7. 求める場合の数は $n(\overline{A}\cup\overline{B})$ である.
  8. \begin{align} &n(\overline{A}\cup\overline{B})\\ =&n(\overline{A\cap{B}})\\ =&n(U)-n(A\cap{B})\\ =&100-4=\boldsymbol{96} \end{align}