集合と位相の問題

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

$f:A\to A$ を、各元 $x$ から $f(x)$ へ矢印を引いたグラフとみる。像を $B=f(A)$ とおく。

• $f\circ f=f$ のとき：$y\in B$ をとると、ある $x$ で $y=f(x)$ と書ける。よって $f(y)=f(f(x))=f(x)=y$ となり、像の元はすべて自分自身に矢印が戻る（不動点である）。
• 逆に、像の元がすべて不動点のとき：任意の $x$ について $f(x)\in B$ なので $f(f(x))=f(x)$ となり、$f\circ f=f$ が成り立つ。

したがって
$$f\circ f=f⟺\text{像 }B\text{ の各元 }y\text{ について }f(y)=y$$
である。グラフでいえば、「像の元はすべて自分へのループをもち、像以外の元は 1 本の矢印で直接像の元に入る（深さ 1 以下）」という形である。

手順 2：像を決めてから写像を数える。

像 $B$ の元の個数を $k$（$1\le k\le 4$）とする。

• 像 $B$ の選び方は ${}_4{\mathrm{C}}_k$ 通り。
• $B$ の元の行き先は自分自身に決まる（1 通り）。
• $B$ 以外の $4-k$ 個の元は、それぞれ $B$ の $k$ 個の元のどれに移ってもよい。行き先は $B$ の中なので像は $B$ からはみ出さない。また $B$ の各元は自分自身の像なので、像はちょうど $B$ になる。よって $k^{4-k}$ 通り（重複順列）。

したがって、像の元の個数が $k$ である条件を満たす写像は ${}_4{\mathrm{C}}_k\cdot k^{4-k}$ 個ある。

手順 3：和の法則でまとめる。

$$\begin{array}{rl}k=1& :{}_4{\mathrm{C}}_1\cdot 1^3=4\cdot 1=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\cdot 1=1\end{array}$$

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

よって求める個数は $41$ である。

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

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

そこで、像の大きさ $k$ ごとに数える。像 $B$ を選ぶ方法は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通りである。$B$ の元は自分自身に写す。残りの $4-k$ 個の元は $B$ の任意の元に写せるので、$k^{4-k}$ 通りある。ただし像がちょうど $B$ になる必要があるが、$B$ の元は固定点なので像は必ず $B$ を含み、$B$ 以外には写さないので像は $B$ に一致する。

• $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$

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

検算: $n=2$ のときは同じ公式で $2+1=3$ となる。実際に冪等写像は恒等写像と 2 つの定値写像の計 3 個で、一致する。