写像・単射の個数と集合の濃度

有限集合 $A, B$ （ $∣ A ∣ = m, ∣ B ∣ = n$ ）について、次の値を使って、部分集合と写像の組のような集合の濃度を求められる: 写像の個数 $n^{m}$ 、単射の個数 $_{n} P_{m}$ 、べき集合の濃度 $∣ P (A) ∣ = 2^{m}$ 、直積の濃度 $∣ A \times B ∣ = mn$

前提

組合せ（数学A 場合の数と確率）

この技能までの道筋（5 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）

説明

有限集合どうしの写像の個数、単射の個数、部分集合全体の個数、直積の要素の個数を、元の個数 $m, n$ だけから求められるようになります。これらを組み合わせると、「部分集合と写像の組」のように少し複雑に見える集合の要素の個数（濃度）も、かけ算だけで求められます。写像の数え上げ、確率の場合の数、組合せ論の問題などで使います。

なぜそうしてよいのか

記号を決めます。有限集合 $X$ の元の個数（濃度）を $∣ X ∣$ と書きます。 $∣ A ∣ = m, ∣ B ∣ = n$ とし、 $A$ から $B$ への写像全体の集合を $B^{A}$ と書きます。写像 $f : A \to B$ は、 $A$ の各元 $a$ に $B$ の元 $f (a)$ を 1 つずつ割り当てるものです。そこで $A$ の元を $a_{1}, \dots, a_{m}$ と並べ、行き先を順に選ぶと考えます。各 $a_{i}$ の行き先は $n$ 通りずつあり、その選び方はほかの元の行き先に左右されません。よって積の法則（重複順列）により $∣ B^{A} ∣ = n^{m}$ です。次に、 $f$ が単射であるとは、 $a \neq = a^{'}$ ならば $f (a) \neq = f (a^{'})$ となることです。このとき行き先はすべて異なっていなければなりません。 $a_{1}$ の行き先は $n$ 通り、 $a_{2}$ は $a_{1}$ の行き先を除いた $n - 1$ 通り、…、 $a_{m}$ は $n - m + 1$ 通りです。よって $m \leq n$ のとき、単射の個数は $_{n} P_{m} = n (n - 1) \dots (n - m + 1)$ です。 $m > n$ のときは、 $a_{1}, \dots, a_{n}$ で $B$ の元を使い切るので、 $a_{n + 1}$ の行き先が残りません。したがって単射は存在せず、個数は $0$ です。積 $n (n - 1) \dots (n - m + 1)$ をこの場合にもそのまま書くと、 $a_{n + 1}$ に対応する因数が $n - n = 0$ になるので、積の値も $0$ になり、数えた結果と一致します。

$A$ の部分集合全体の集合（べき集合）を $P (A)$ と書きます。部分集合 $S$ を 1 つ決めることは、 $A$ の各元について「 $S$ に入れる・入れない」の 2 通りを決めることと同じです。したがって積の法則より $∣ P (A) ∣ = 2^{m}$ です。空集合 $\emptyset$ （全部「入れない」）と $A$ 自身（全部「入れる」）も部分集合に含まれます。確認のため、元の個数で分類して数えることもできます。元が $k$ 個の部分集合は $_{m} C_{k}$ 個あるので、和の法則より $∣ P (A) ∣ = \sum_{k = 0}^{m}_{m} C_{k}$ です。2 通りの数え方は同じ集合を数えているので、 $\sum_{k = 0}^{m}_{m} C_{k} = 2^{m}$ が成り立ちます（二項定理を知っていれば、 $(1 + 1)^{m}$ を展開した式とも一致します）。

直積 $A \times B = {(a, b) ∣ a \in A, b \in B}$ は、 $a$ を $m$ 通り、 $b$ を $n$ 通り、互いに無関係に選んだ組の集合です。積の法則より $∣ A \times B ∣ = mn$ となります。この考え方は $A, B$ に限らず、どんな有限集合 $X, Y$ にも使えます。「〇〇と△△の組」の集合は直積 $X \times Y$ なので、 $∣ X \times Y ∣ = ∣ X ∣ ∣ Y ∣$ のように、各成分の個数をかければ全体の個数が求められます。

手順

数えたい集合を「何と何の組か」に分解し、直積 $X_{1} \times X_{2} \times \dots$ の形に書く。
各成分 $X_{i}$ が、写像全体 $B^{A}$ 、単射全体、べき集合 $P (A)$ 、直積のどれにあたるかを見分ける。写像の向き（定義域が $A$ 、行き先が $B$ ）も確認する。
各成分の個数を求める。写像全体なら $n^{m}$ 、単射なら $_{n} P_{m} = n (n - 1) \dots (n - m + 1)$ （ $m > n$ なら $0$ ）、べき集合なら $2^{m}$ 、直積なら $mn$ を使う。ここで $m$ は定義域の元の個数、 $n$ は行き先の集合の元の個数である。
積の法則で全体の個数を求める: $∣ X_{1} \times X_{2} \times \dots ∣ = ∣ X_{1} ∣ ∣ X_{2} ∣ \dots$ 。

例題

$A = {1, 2, 3}$ 、 $B = {p, q, r, s}$ とする。 $A$ の部分集合 $S$ と単射 $f : A \to B$ の組 $(S, f)$ 全体の集合 ${(S, f) ∣ S \subseteq A, f : A \to B は単射}$ の濃度を求めよ。

例題の解答

手順 1: この集合は、べき集合 $P (A)$ と「 $A$ から $B$ への単射全体の集合」 $I$ の直積 $P (A) \times I$ である。
手順 2: 第 1 成分はべき集合 $P (A)$ 、第 2 成分は単射全体である。単射の定義域は $A$ なので $m = 3$ 、行き先は $B$ なので $n = 4$ である。
手順 3: $∣ P (A) ∣ = 2^{3} = 8$ である（ $\emptyset$ と $A$ も含む）。 $m = 3 \leq n = 4$ なので $∣ I ∣ =_{4} P_{3} = 4 \cdot 3 \cdot 2 = 24$ である。
手順 4: 積の法則より $∣ P (A) \times I ∣ = 8 \times 24 = 192$ となる。

答え: $192$

よくある誤り

写像の個数を $m^{n}$ としてしまう誤り。正しくは、定義域の各元が行き先を $n$ 通りずつ選ぶので $n^{m}$ である。例: $∣ A ∣ = 3, ∣ B ∣ = 4$ なら $4^{3} = 64$ であり、 $3^{4} = 81$ ではない。
単射の個数を $_{n} C_{m}$ としてしまう誤り。どの元がどこへ行くかで写像は区別されるので、順序を考えた $_{n} P_{m}$ が正しい。例: $∣ A ∣ = 3, ∣ B ∣ = 4$ なら $_{4} P_{3} = 24$ であり、 $_{4} C_{3} = 4$ ではない。
$m > n$ なのに $_{n} P_{m} = \frac{n !}{( n - m )!}$ に当てはめてしまう誤り。 $n - m < 0$ なので $(n - m)!$ は定義されず、計算が破綻する。無理に計算して $0$ でない値を答えるのも誤りである。正しくは、積 $n (n - 1) \dots (n - m + 1)$ に因数 $0$ が現れるので $0$ （ $n + 1$ 番目の元には選べる行き先が残っていないので $0$ ）である。例: $∣ A ∣ = 5, ∣ B ∣ = 3$ なら $3 \cdot 2 \cdot 1 \cdot 0 \cdot (- 1) = 0$ で、単射は $0$ 個。
べき集合の濃度を $m^{2}$ としたり、空集合や $A$ 自身を数え忘れて $2^{m} - 1$ や $2^{m} - 2$ としてしまう誤り。正しくは $∣ P (A) ∣ = 2^{m}$ である。例: $m = 3$ なら $8$ 個で、 $\emptyset$ と $A$ も含む。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

全射の個数（大学数学集合と位相）
写像の合成と像の構造（大学数学集合と位相）
可算集合（大学数学集合と位相）
有限集合上の位相（大学数学集合と位相）