全射の個数

包除原理で全射 $f : A \to B$ の個数 $\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{m}$ を求められる。 $f (1) \neq = f (2)$ のような条件がついた全射の個数も数えられる

前提

写像・単射の個数と集合の濃度（大学数学集合と位相）
一般の包除原理（大学数学離散数学・組合せ論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
写像・単射の個数と集合の濃度（大学数学集合と位相）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）
一般の包除原理（大学数学離散数学・組合せ論）

説明

有限集合 $A$ （ $∣ A ∣ = m$ ）から有限集合 $B$ （ $∣ B ∣ = n$ ）への写像のうち、 $B$ のどの元も少なくとも 1 回は値として取られるもの（全射）の個数を求めます。これは「区別できる $m$ 個の玉を区別できる $n$ 個の箱に、空箱がないように入れる方法の数」や「 $m$ 人を $n$ 個の係に、どの係も 1 人以上になるように割り振る方法の数」と同じです。包除原理を使うと $\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{m}$ という式で計算できます。 $f (1) \neq = f (2)$ のような条件がついた全射も、同じ考え方で数えられます。

なぜそうしてよいのか

全射を直接数えるのは難しいので、逆の「値として取られない元がある」写像を数えて引きます。 $B = {b_{1}, \dots, b_{n}}$ とし、写像 $f : A \to B$ 全体（ $n^{m}$ 個）の中で、条件 $C_{j}$ を「 $b_{j}$ が値として取られない」（つまり $b_{j} \in / f (A)$ ）と定めます。 $f$ が全射であることは、どの $C_{j}$ も満たさないこと、すなわち $f \in C_{1} \cap \dots \cap C_{n}$ と同じです。そこで一般の包除原理が使えます。

$k$ 個の条件 $C_{j_{1}}, \dots, C_{j_{k}}$ を同時に満たす写像は、値がすべて $B ∖ {b_{j_{1}}, \dots, b_{j_{k}}}$ （元は $n - k$ 個）に入る写像です。その個数は、行き先の集合が $n - k$ 個の元をもつ写像の個数なので $(n - k)^{m}$ です。この値は、どの $k$ 個を選んだかによらず同じです（対称な条件）。 $k$ 個の選び方は $(k n)$ 通りなので、包除原理より
$# {全射 A \to B} = k = 0 \sum n (- 1)^{k} (k n) (n - k)^{m}$
となります。 $k = n$ の項は $0^{m}$ で、 $m \geq 1$ なら $0$ です。また $m < n$ のときは全射が存在しないので、この和は $0$ になります。

条件つきの場合も考え方は同じです。たとえば $f (1) \neq = f (2)$ を満たす全射は、「全射全体」から「 $f (1) = f (2)$ を満たす全射」を引けば求まります。 $f (1) = f (2)$ のとき、 $1$ と $2$ は同じ値をとるので 1 つの元にまとめてよく、これは $m - 1$ 個の元をもつ集合から $B$ への全射と 1 対 1 に対応します。

手順

$m = ∣ A ∣$ （定義域の元の個数）と $n = ∣ B ∣$ （終域の元の個数）を確かめる。 $m < n$ なら全射は存在しないので、答えは $0$ である。
$B$ の各元 $b_{j}$ について、条件 $C_{j}$ を「 $b_{j}$ が値として取られない」と定める。全射とは、どの $C_{j}$ も満たさない写像のことである。
$k$ 個の条件を同時に満たす写像の個数を求める。値が残りの $n - k$ 個の元に入る写像なので $(n - k)^{m}$ 個であり、 $k$ 個の選び方は $(k n)$ 通りある。
包除原理で $\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{m}$ を計算する。 $m \geq 1$ なら $k = n$ の項は $0$ である。
$f (1) \neq = f (2)$ のような条件がつくときは、（全射全体の個数） $-$ （ $f (1) = f (2)$ を満たす全射の個数）を計算する。後者は、 $1$ と $2$ をまとめた $m - 1$ 元集合から $B$ への全射の個数に等しい。

例題

$A = {1, 2, 3, 4, 5}$ 、 $B = {a, b, c}$ とする。全射 $f : A \to B$ の個数を求めよ。

例題の解答

手順1: $m = 5$ 、 $n = 3$ であり、 $m \geq n$ なので全射は存在しうる。
手順2: 条件 $C_{a}, C_{b}, C_{c}$ を、それぞれ「 $a$ （ $b$ 、 $c$ ）が値として取られない」と定める。全射は、これらのどれも満たさない写像である。
手順3: $k$ 個の条件を同時に満たす写像は $(3 - k)^{5}$ 個ある。 $k = 0$ のとき $3^{5} = 243$ 、 $k = 1$ のとき $2^{5} = 32$ 、 $k = 2$ のとき $1^{5} = 1$ 、 $k = 3$ のとき $0^{5} = 0$ である。
手順4: 包除原理より
$(0 3) 3^{5} - (1 3) 2^{5} + (2 3) 1^{5} - (3 3) 0^{5} = 243 - 96 + 3 - 0 = 150.$
したがって、全射は $150$ 個である。

答え: $150$

よくある誤り

第 1 項と第 2 項だけで $n^{m} - n (n - 1)^{m}$ としてしまう誤り。2 つの元がともに取られない写像を 2 回引いているので、足し戻す必要がある。正しくは $m = 5, n = 3$ のとき $243 - 96 + 3 = 150$ であり、 $243 - 96 = 147$ ではない。
「まず $n$ 個の元に 1 つずつ行き先を割り当て、残りは自由に決める」として $(n m) n! n^{m - n}$ と数えてしまう誤り。同じ写像を何回も数えてしまう。例えば $m = 4, n = 3$ でこの式は $4 \cdot 6 \cdot 3 = 72$ になるが、正しくは $3^{4} - 3 \cdot 2^{4} + 3 \cdot 1^{4} = 81 - 48 + 3 = 36$ である。
$k$ 個の元が取られない写像の個数を $(n - k)^{m}$ ではなく $n^{m - k}$ や $(n - 1)^{m - k}$ としてしまう誤り。正しくは、定義域の $m$ 個の元のそれぞれが、残った $n - k$ 個の元のどれかに移るので $(n - k)^{m}$ である。
$f (1) \neq = f (2)$ の条件で、 $f (1) = f (2)$ となる全射の個数を、 $m - 2$ 元集合から $B$ への全射の個数（ $1, 2$ を取り除いたもの）としてしまう誤り。 $1, 2$ の共通の値も含めて $B$ のすべての元が取られればよいので、 $1$ と $2$ をまとめた $m - 1$ 元集合からの全射として数える。例えば $m = 4, n = 3$ では $f (1) = f (2)$ の全射は $3! = 6$ 個で、答えは $36 - 6 = 30$ である。

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

全射の個数

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題