写像の合成と像の構造

写像 $f : A \to A$ を、各元から矢印を引いたグラフとみられる。 $f \circ f = f$ や $f \circ f = f \circ f \circ f$ のような合成の条件を像の元・深さの条件に言い換え、条件を満たす写像の個数を求められる

前提

写像・単射の個数と集合の濃度（大学数学集合と位相）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
写像・単射の個数と集合の濃度（大学数学集合と位相）

説明

有限集合 $A$ から自分自身への写像 $f : A \to A$ は、各元 $x$ から $f (x)$ へ矢印を 1 本ずつ引いた図（矢印のグラフ）として描けます。この見方を使うと、 $f \circ f = f$ や $f \circ f = f \circ f \circ f$ のような合成の式を、「像の元は動かない」「何歩で動かない元に着くか」という図の形の条件に言い換えられます。条件を満たす写像の個数は、図の形を決める元の選び方と矢印の引き方を数えれば求まります。

なぜそうしてよいのか

合成は $(g \circ f) (x) = g (f (x))$ と定め、 $f$ を $m$ 回合成したものを $f^{m}$ と書きます。 $f \circ f = f$ は「すべての $x \in A$ で $f (f (x)) = f (x)$ 」という意味です。 $y = f (x)$ とおくと、 $x$ が $A$ 全体を動くとき $y$ は像 $f (A)$ 全体を動きます。よってこの条件は「像のどの元 $y$ も $f (y) = y$ （動かない元＝固定点）」と同じです。逆に像の元がすべて固定点なら、 $f (f (x)) = f (x)$ が成り立ちます。図でいえば、矢印を 1 歩たどると必ず固定点に着き、そこでは自分自身へ戻る矢印（ループ）しかない形です。

この形の写像を数えます。固定点の集合を $S$ （ $∣ S ∣ = k$ ）とします。 $S$ の元の行き先は自分自身に決まります。 $S$ の外の $n - k$ 個の元は、 $S$ のどこへ行ってもかまいません。このとき像はちょうど $S$ になり、条件を満たします。 $S$ の外の各元の行き先は $k$ 通りなので、行き先の決め方は前提の技能の写像の個数で $k^{n - k}$ 通りです。 $S$ の選び方は $_{n} C_{k}$ 通りなので、 $k$ について和をとれば総数が出ます。

同じ考え方は $f^{2} = f^{3}$ にも使えます。これは「 $f^{2} (A)$ の元がすべて固定点」と同じ意味です。各元 $x$ について、 $f^{m} (x)$ が固定点になる最小の $m \geq 0$ を $x$ の深さと呼ぶことにします。すると $f^{2} = f^{3}$ は「すべての元の深さが $2$ 以下」と言い換えられます。一般に $f^{m} = f^{m + 1}$ は「すべての元の深さが $m$ 以下」と同じです。

手順

条件の式を、各元 $x$ についての等式 $f (f (x)) = f (x)$ などに書き直す（ $(g \circ f) (x) = g (f (x))$ ）。
$y = f (x)$ や $y = f^{2} (x)$ とおき、条件を「像 $f (A)$ （または $f^{2} (A)$ ）の元はすべて固定点」と言い換える。深さで言えば、 $f^{m} = f^{m + 1}$ は「すべての元の深さが $m$ 以下」になる。
元を深さで分類する。深さ $0$ が固定点の集合 $S$ 、深さ $1$ は $S$ へ直接行く固定点でない元、深さ $2$ は深さ $1$ の元へ行く元。各層に属する元を組合せで選ぶ。
各層の元の行き先を数える。固定点は自分自身の 1 通り、深さ $d$ の元は深さ $d - 1$ の層の元のどれか。積の法則を使う。例えば $f \circ f = f$ なら $∣ S ∣ = k$ のとき $_{n} C_{k} k^{n - k}$ 通り。
層の大きさについて和の法則で足し合わせる。 $f \circ f = f$ なら $k = 1 \sum n_{n} C_{k} k^{n - k}$ 。 $f^{2} = f^{3}$ なら、固定点 $k$ 個・深さ $1$ が $j$ 個として $k, j \sum_{n} C_{k}_{n - k} C_{j} k^{j} j^{n - k - j}$ （ $0^{0} = 1$ とする）。

例題

$A = {1, 2, 3, 4}$ とする。写像 $f : A \to A$ のうち、 $f \circ f = f$ を満たすものの個数を求めよ。

例題の解答

手順1: 条件は、すべての $x \in A$ で $f (f (x)) = f (x)$ が成り立つことである。

手順2: $y = f (x)$ とおくと、 $y$ は像 $f (A)$ 全体を動く。よって条件は「像の元はすべて固定点」と同じであり、像は固定点の集合 $S$ に一致する。 $A$ は空でないので、像は空でなく $∣ S ∣ = k \geq 1$ である。

手順3: 深さ $0$ の層 $S$ の選び方は $_{4} C_{k}$ 通りである。残りの $4 - k$ 個はすべて深さ $1$ になる。

手順4: $S$ の元の行き先は自分自身に決まる。残りの $4 - k$ 個の元はそれぞれ $S$ の $k$ 個のどれかへ行くので、 $k^{4 - k}$ 通りある。
- $k = 1$ : $_{4} C_{1} \cdot 1^{3} = 4$
- $k = 2$ : $_{4} C_{2} \cdot 2^{2} = 24$
- $k = 3$ : $_{4} C_{3} \cdot 3^{1} = 12$
- $k = 4$ : $_{4} C_{4} \cdot 4^{0} = 1$

手順5: 和の法則より、 $4 + 24 + 12 + 1 = 41$ 個である。

答え: $41$

よくある誤り

$f \circ f = f$ から $f$ は恒等写像だと決めてしまう誤り。正しくは、動かないのは像の元だけである。例えば定数写像 $f (x) = 1$ も $f (f (x)) = 1 = f (x)$ を満たす。
固定点の集合 $S$ を選んだあと、すべての元の行き先を $S$ から選ぶとして $_{n} C_{k} k^{n}$ と数えてしまう誤り。 $S$ の元を $S$ の別の元へ送ると、像の元が固定点でなくなる。正しくは $S$ の元は自分自身に固定され、 $_{n} C_{k} k^{n - k}$ となる。
$f^{2} = f^{3}$ を「 $f (A)$ の元がすべて固定点」と言い換えてしまう誤り。それは $f^{2} = f$ の条件である。正しくは「 $f^{2} (A)$ の元がすべて固定点」、つまりすべての元の深さが $2$ 以下という条件である。
深さ $\leq 2$ を数えるとき、深さ $2$ の元の行き先を「固定点または深さ $1$ の元」として $(k + j)^{n - k - j}$ と数えてしまう誤り。固定点へ行く元は深さ $1$ なので、二重に数えてしまう。正しくは深さ $2$ の元は深さ $1$ の元へ行き、 $j^{n - k - j}$ 通りである。

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

入口の問題

この技能を使う問題

難易度 4（大学院入試の標準レベル）
$A = {1, 2, 3, 4, 5}$ とする。写像 $f : A \to A$ のうち、合成について
$f \circ f = f \circ f \circ f$
を満たすものの個数を求めよ。