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

最終更新

有限集合の要素の個数を、重複も数え落としもなく求めるには、対象をどのように分ければよいでしょうか。本記事では有限集合とその分割を最初の数学的対象とし、和の法則と積の法則を導きます。さらに、補集合による数え上げと、二つ・三つの集合に対する包除を用いて個数を求める方法まで扱います。

1 和の法則と積の法則

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

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

∣A1∪⋯∪Am∣=∣A1∣+⋯+∣Am∣\left|A_1\cup\cdots\cup A_m\right|=|A_1|+\cdots+|A_m|

が成り立つ。

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

選択を順に行い、前の選択によって後の選択肢の個数が変わらないときは、個数を掛けます。

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

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

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

2 重複を引く

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

定理 2.1 (二つの有限集合の包除). 有限集合A,BA,Bについて、

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|

が成り立つ。

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

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

50+33−16=6750+33-16=67

個である。

全体集合UUのうち条件を満たす集合をAAとすると、条件を満たさないものはU∖AU\setminus Aです。

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

∣U∖A∣=∣U∣−∣A∣|U\setminus A|=|U|-|A|

が成り立つ。

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

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

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

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣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∈A∪B∪Cx\in A\cup B\cup Cを取り、xxがA,B,CA,B,Cのうちちょうどrr個に属するとする。r=1r=1のとき右辺におけるxxの寄与は11である。r=2r=2のときは、最初の三項で二度数え、二集合の共通部分の項で一度引くので、寄与は2−1=12-1=1である。r=3r=3のときは、最初の三項で三度数え、二集合の共通部分の三項で三度引き、最後に一度足すので、寄与は3−3+1=13-3+1=1である。したがって、右辺はA∪B∪CA\cup B\cup Cの各要素をちょうど一度ずつ数える。▨

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

3 演習

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

解答.

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

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

解答.

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

問題 3.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=7450+33+20-16-10-6+3=74

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

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

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

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

  1. 例題 1

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

  2. 例題 2

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

演習

問題を解いてから「解答・解説」を開けます。

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

演習を読み込み中…

前提記事