有限集合の要素の個数 | 場合の数と確率統計

1 和の法則と積の法則

場合を互いに重ならない組に分けるときは、各組に含まれる場合の個数を足します。

定理 1.1 (和の法則). $m\in\Z_{\geq 1}$ とし、有限集合 $A_1,\ldots,A_m$ はどの二つも共通の要素をもたないとする。このとき

\left|A_1\cup\cdots\cup A_m\right|=|A_1|+\cdots+|A_m|

が成り立つ。

証明. $x\in A_1\cup\cdots\cup A_m$ を取る。集合がどの二つも共通の要素をもたないので、 $x$ が属する $A_i$ はただ一つである。したがって、右辺は和集合の各要素をちょうど一度ずつ数えるため、左辺と等しい。▨

選択を順に行うとき、前の選択によって後の選択肢の個数が変わらなければ、各段階の選択肢の個数を掛けます。

定理 1.2 (積の法則). $a,b\in\Z_{\geq 0}$ とする。第1段階の選択が $a$ 通りあり、どの第1段階の選択に対しても第2段階の選択が $b$ 通りあるならば、順序を含めた二段階の選択結果は $ab$ 通りある。

証明. 第1段階の選択ごとに、その選択から始まる二段階の選択結果をまとめる。各組には $b$ 個の結果があり、異なる第1段階の選択に対応する組は互いに重ならない。このような組が $a$ 個あるので、和の法則により結果の総数は $b$ を $a$ 回足した $ab$ である。▨

例 1.3. 0から9までの数字を用いて3桁の列を作る。各桁には10通りの選択があり、数字の重複を許すので、積の法則により列は $10^3=1000$ 通りある。

2 包除原理と補集合の要素数

二つの集合が重なる場合には、共通部分を二度数えた分を引きます。

定理 2.1. 有限集合 $A,B$ について、

|A\cup B|=|A|+|B|-|A\cap B|

が成り立つ。

証明. $x\in A\cup B$ を取る。 $x\in A\cap B$ ならば $|A|+|B|$ では $x$ を二度数え、それ以外ならば一度だけ数える。したがって、 $A\cap B$ の各要素について一度ずつ引くと、 $A\cup B$ の各要素をちょうど一度ずつ数える。▨

例 2.2. 1以上100以下の整数のうち、2の倍数または3の倍数であるものを数える。2の倍数は50個、 3の倍数は33個、両方の倍数である6の倍数は16個なので、

50+33-16=67

個である。

全体集合 $U$ の要素のうち条件を満たすもの全体を $A$ とすると、条件を満たさない要素全体は $U\setminus A$ です。

公式 2.3 (補集合による数え上げ). 有限な全体集合 $U$ とその部分集合 $A\subseteq U$ について、

|U\setminus A|=|U|-|A|

が成り立つ。

$U$ は $A$ と $U\setminus A$ の互いに重ならない和集合なので、定理 1.1を用いると上の公式が得られます。

三つの集合では、二つずつの共通部分の要素の個数を引いた後に、三つすべての共通部分の要素の個数を足し戻します。

公式 2.4 (三つの有限集合の包除). 有限集合 $A,B,C$ について、

|A\cup B\cup C| =|A|+|B|+|C| -|A\cap B|-|B\cap C|-|C\cap A| +|A\cap B\cap C|

が成り立つ。

証明. $x\in A\cup B\cup C$ を取り、 $x$ が $A,B,C$ のうちちょうど $r$ 個に属するとする。 $r=1$ のとき右辺における $x$ の寄与は $1$ である。 $r=2$ のときは、最初の三項で二度数え、二集合の共通部分の項で一度引くので、寄与は $2-1=1$ である。 $r=3$ のときは、最初の三項で三度数え、二集合の共通部分の三項で三度引き、最後に一度足すので、寄与は $3-3+1=1$ である。したがって、右辺は $A\cup B\cup C$ の各要素をちょうど一度ずつ数える。▨

任意個の有限集合に対する包除の一般形は§B4.4 包除原理の一般形で扱います。

3 例題

レベル1 — 和集合の要素数

次の条件を満たす整数の個数を求めよ。

解法の型n(A $\cup$ B) $=$ n(A) + n(B) − n(A $\cap$ B)。共通部分は lcm(a, b) の倍数

例 3.1.

1 \text{ から } 100 \text{ までの整数のうち、} 4 \text{ の倍数または } 6 \text{ の倍数であるものの個数}

答 $33$

注意 n(A) $=$ 25, n(B) $=$ 16, $n(A\cap B) =$ 8

例 3.2.

1 \text{ から } 60 \text{ までの整数のうち、} 2 \text{ の倍数または } 4 \text{ の倍数であるものの個数}

答 $30$

注意 n(A) $=$ 30, n(B) $=$ 15, $n(A\cap B) =$ 15

4 演習

問題 4.1. 1以上200以下の整数のうち、4の倍数または6の倍数であるものの個数を求めよ。

解答.

4の倍数は50個、6の倍数は33個であり、両方の倍数である12の倍数は16個ある。二集合の包除により、求める個数は $50+33-16=67$ 個である。▨

問題 4.2. 5種類の上着と3種類のズボンから一つずつ選ぶ組は何通りあるか。

解答.

どの上着を選んでもズボンの選択は3通りある。積の法則により、組は $5\cdot3=15$ 通りある。▨

問題 4.3. 1以上100以下の整数のうち、2、3、5のいずれでも割り切れないものの個数を、三つの集合の公式を用いて求めよ。

解答.

2、3、5の倍数はそれぞれ50個、33個、20個ある。二つの条件を同時に満たす6、10、15の倍数はそれぞれ16個、10個、6個あり、三つの条件を同時に満たす30の倍数は3個ある。したがって、 2、3、5の倍数の和集合は

50+33+20-16-10-6+3=74

個である。補集合による数え上げから、求める個数は $100-74=26$ 個である。▨

レベル1 — 和集合の要素数

次の条件を満たす整数の個数を求めよ。

解法の型n(A $\cup$ B) $=$ n(A) + n(B) − n(A $\cap$ B)。共通部分は lcm(a, b) の倍数

問題 4.4.

1 \text{ から } 60 \text{ までの整数のうち、} 5 \text{ の倍数または } 4 \text{ の倍数であるものの個数}

解答.

答 $24$

注意 n(A) $=$ 12, n(B) $=$ 15, $n(A\cap B) =$ 3▨

問題 4.5.

1 \text{ から } 60 \text{ までの整数のうち、} 5 \text{ の倍数または } 7 \text{ の倍数であるものの個数}

解答.

答 $19$

注意 n(A) $=$ 12, n(B) $=$ 8, $n(A\cap B) =$ 1▨

問題 4.6.

1 \text{ から } 60 \text{ までの整数のうち、} 5 \text{ の倍数または } 6 \text{ の倍数であるものの個数}

解答.

答 $20$

注意 n(A) $=$ 12, n(B) $=$ 10, $n(A\cap B) =$ 2▨

§B4.1有限集合の要素の個数

1 和の法則と積の法則

2 包除原理と補集合の要素数

3 例題

4 演習

前提記事