集合と位相の問題

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

$f\circ f=f$ は、すべての $x\in A$ について $f(f(x))=f(x)$ が成り立つことである。$y=f(x)$ とおくと、これは「像 $f(A)$ のどの元 $y$ についても $f(y)=y$」ということである。

逆に、像の元がすべて $f$ で動かない（固定される）とする。任意の $x$ について $f(x)$ は像の元なので $f(f(x))=f(x)$ となり、$f\circ f=f$ が成り立つ。

よって
$$f\circ f=f⟺\text{像 }f(A)\text{ の元はすべて }f\text{ で固定される}$$
である。矢印のグラフでいえば、「どの元も 1 回矢印をたどると、自分に矢印が戻る元（ループをもつ元）に着き、そこで止まる」という形である。

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

像を $S=f(A)$、$|S|=k$ とする（$A$ は空でないので $1\le k\le 4$）。条件を満たす $f$ は次のように決まる。
- $S$ の元は自分自身に移す（選び方は 1 通り）。
- $S$ に入らない $4-k$ 個の元は、それぞれ $S$ のどれか $k$ 個の元に移す。

このとき $S$ の元は固定されるので像はちょうど $S$ になり、手順 1 の条件も満たす。逆に条件を満たす $f$ は必ずこの形である。$S$ の外の元の行き先の決め方は重複順列で $k^{4-k}$ 通りである。

$S$ の選び方は ${}_4{\mathrm{C}}_k$ 通りなので、像の大きさが $k$ のものは ${}_4{\mathrm{C}}_k{k}^{4-k}$ 個である。

手順 3：和の法則で合計する。

• $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$（恒等写像）

これらを合計して
$$4+24+12+1=41$$
よって求める個数は $41$ である。

$f\circ f=f$ は、$f$ の像 $B=f(A)$ の各元 $b$ で $f(b)=b$ となることと同値である。

(⇒) $b=f(a)$ とすると $f(b)=f(f(a))=f(a)=b$。
(⇐) 任意の $a$ について $f(a)\in B$ なので $f(f(a))=f(a)$。

そこで像の大きさ $k$ で場合分けする。像 $B$ を選ぶ方法は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通り。$B$ の元は固定される。残り $4-k$ 個の元は、それぞれ $B$ のどの元に写してもよいので $k^{4-k}$ 通り（像がちょうど $B$ になることは $B$ の元が固定されることから保証される）。

個数は ${\sum }_{k=1}^4\left(\genfrac{}{}{0ex}{}{4}{k}\right)k^{4-k}$ である。
- $k=1$: $4\cdot 1^3=4$
- $k=2$: $6\cdot 2^2=24$
- $k=3$: $4\cdot 3^1=12$
- $k=4$: $1\cdot 4^0=1$

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

検算として、$n=2$ の場合は $\left(\genfrac{}{}{0ex}{}{2}{1}\right)1^1+\left(\genfrac{}{}{0ex}{}{2}{2}\right)2^0=2+1=3$。実際に $f$ は恒等写像と 2 つの定数写像の 3 個で、一致する。また、列 1, 3, 10, 41 は既知の「べき等写像の個数」(OEIS A000248) と一致する。