集合と位相の問題

手順1：条件を像の言葉に言い換える。

$f$ の像を $f(A)=\{f(x)\mid x\in A\}$ とする。$f\circ f=f$ は、次の条件と同値であることを示す。
$$\text{像 }f(A)\text{ のすべての元 }y\text{ について }f(y)=y$$

• $f\circ f=f$ を仮定する。$y\in f(A)$ とすると、ある $x$ で $y=f(x)$ と書ける。このとき $f(y)=f(f(x))=f(x)=y$ となる。
• 逆に、像の元がすべて $f$ で動かないと仮定する。任意の $x$ について $f(x)\in f(A)$ なので、$f(f(x))=f(x)$ となる。よって $f\circ f=f$ である。

各元 $x$ から $f(x)$ へ矢印を引いたグラフで考えると、この条件は「像の元は自分自身への矢印（ループ）をもち、それ以外の元はどれか 1 つの像の元へ直接矢印を引く」という形になる。矢印をたどる長さ（深さ）は高々 $1$ である。

手順2：像 $B$ を決めて数える。

像を $B\subseteq A$、$|B|=k$（$1\le k\le 4$）とする。

• $B$ の元は自分自身に移す。移し方は $1$ 通りである。
• $B$ に入らない $4-k$ 個の元は、それぞれ $B$ の $k$ 個の元のどれに移してもよい。重複順列により $k^{4-k}$ 通りである。

このとき $B$ の各元は自分自身の像になっているので、像はちょうど $B$ になる。

$B$ の選び方は ${}_4{\mathrm{C}}_k$ 通りある。よって $|B|=k$ となる写像は ${}_4{\mathrm{C}}_k\cdot k^{4-k}$ 個である。

手順3：和をとる。

• $k=1$：${}_4{\mathrm{C}}_1\cdot 1^3=4$
• $k=2$：${}_4{\mathrm{C}}_2\cdot 2^2=6\cdot 4=24$
• $k=3$：${}_4{\mathrm{C}}_3\cdot 3^1=4\cdot 3=12$
• $k=4$：${}_4{\mathrm{C}}_4\cdot 4^0=1$

和の法則より、求める個数は
$$4+24+12+1=41$$
である。

$f\circ f=f$ であることは、$f$ の像 $f(A)$ の各元 $y$ について $f(y)=y$ が成り立つことと同値である。

（理由）$f\circ f=f$ ならば、$y=f(x)$ に対して $f(y)=f(f(x))=f(x)=y$ となる。逆に、像の元がすべて固定点なら $f(f(x))=f(x)$ である。

像の元数を $k$ とすると、像の選び方は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通りである。像の元は $f$ により自分自身に写る。像に含まれない $4-k$ 個の元は、像の $k$ 個の元のどれかに写せばよいので、それぞれ $k$ 通りあり、$k^{4-k}$ 通りとなる。

• $k=1$: $\left(\genfrac{}{}{0ex}{}{4}{1}\right)\cdot 1^3=4$
• $k=2$: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 2^2=24$
• $k=3$: $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 3^1=12$
• $k=4$: $\left(\genfrac{}{}{0ex}{}{4}{4}\right)\cdot 4^0=1$

$k=0$ は $A$ が空でないので起こらない。

合計は $4+24+12+1=41$ である。

検算として $n=2$ の場合を調べる。公式は $\left(\genfrac{}{}{0ex}{}{2}{1}\right)\cdot 1+\left(\genfrac{}{}{0ex}{}{2}{2}\right)\cdot 1=3$ を与える。実際、恒等写像と 2 つの定値写像で 3 個であり、一致する。