集合と位相の問題

条件の言い換え. $f\circ f=f\circ f\circ f$ は、任意の $a\in A$ について $f(f(a))=f(f(f(a)))$、すなわち $b=f(f(a))$ とおくと $f(b)=b$ が成り立つことと同値である。つまり「$\mathrm{Im}(f\circ f)$ のすべての点が $f$ の不動点である」という条件である。

$F=\{a\in A\mid f(a)=a\}$（不動点の集合）とおく。条件は「どの $a$ についても $f(f(a))\in F$」と言い換えられる。このとき $A$ の各元は次のどれか 1 つに属する。
- $F$ の元（不動点）
- $G=\{a\notin F\mid f(a)\in F\}$（1 回で不動点に行く点）
- $H=\{a\notin F\mid f(a)\notin F\}$（1 回では不動点に行かない点）

$a\in H$ ならば $f(a)\notin F$ かつ $f(f(a))\in F$ なので $f(a)\in G$ である。逆に、$A$ を互いに交わらない $F,G,H$ に分け、
- $F$ の元は自分自身へ、
- $G$ の元は $F$ のどれかへ、
- $H$ の元は $G$ のどれかへ

写すように $f$ を定めると、$F$ の元はちょうど不動点全体であり（$G,H$ の元は自分と異なる集合へ写るので不動点でない）、どの $a$ も $f(f(a))\in F$ となるので条件を満たす。また $f$ から $F,G,H$ は一意に決まる。ここで $F=\varnothing$ だと $f(f(a))\in F$ が成り立たないので $|F|\ge 1$、また $G=\varnothing$ なら $H=\varnothing$ でなければならない。

よって $|F|=k(k\ge 1)$, $|G|=j$, $|H|=5-k-j$ として、求める個数は
$$N=\sum _{k=1}^5\left(\genfrac{}{}{0ex}{}{5}{k}\right)\sum _j\left(\genfrac{}{}{0ex}{}{5-k}{j}\right)k^j{j}^{5-k-j}$$
（ただし $0^0=1$ とし、$j=0$ は $5-k-j=0$ のときだけ寄与する）。

計算.

$k=1$（残り 4 個）: $j=1$: $\left(\genfrac{}{}{0ex}{}{4}{1}\right)\cdot 1\cdot 1^3=4$、$j=2$: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 1\cdot 2^2=24$、$j=3$: $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 1\cdot 3^1=12$、$j=4$: $1$。和は $41$ で、$\left(\genfrac{}{}{0ex}{}{5}{1}\right)\cdot 41=205$。

$k=2$（残り 3 個）: $j=1$: $\left(\genfrac{}{}{0ex}{}{3}{1}\right)\cdot 2\cdot 1^2=6$、$j=2$: $\left(\genfrac{}{}{0ex}{}{3}{2}\right)\cdot 2^2\cdot 2^1=24$、$j=3$: $2^3=8$。和は $38$ で、$\left(\genfrac{}{}{0ex}{}{5}{2}\right)\cdot 38=380$。

$k=3$（残り 2 個）: $j=1$: $\left(\genfrac{}{}{0ex}{}{2}{1}\right)\cdot 3\cdot 1=6$、$j=2$: $3^2=9$。和は $15$ で、$\left(\genfrac{}{}{0ex}{}{5}{3}\right)\cdot 15=150$。

$k=4$（残り 1 個）: $j=1$: $4$。$\left(\genfrac{}{}{0ex}{}{5}{4}\right)\cdot 4=20$。

$k=5$: 恒等写像のみで $1$。

したがって
$$N=205+380+150+20+1=756.$$

（確認: 同じ方法で $|A|=3$ のときは $9+6+1=16$ 個となり、全 $27$ 個から長さ $2$ 以上の巡回を含む $11$ 個を除いた数と一致する。）

$f^2=f^3$ は、任意の $x$ について $f(f^2(x))=f^2(x)$、すなわち $f^2(x)$ が $f$ の不動点であることと同値。\n\n関数グラフで言えば、(i) 長さ 2 以上の巡回は存在せず（巡回上の点 $x$ では $f^2(x)$ も巡回上にあり不動点でなければならない）、(ii) どの点も高々 2 回の適用で不動点に到達する、という条件。逆にこの条件なら $f^2(x)$ は不動点で成り立つ。\n\nそこで不動点の集合 $F$ ($|F|=k\ge 1$) を選び、残り $m=5-k$ 個を、$F$ に直接写る集合 $A$ ($|A|=a$) と、$A$ に写る集合 $B$ ($|B|=m-a$) に分ける。個数は\n$$\sum _k\left(\genfrac{}{}{0ex}{}{5}{k}\right)\sum _a\left(\genfrac{}{}{0ex}{}{m}{a}\right)k^a{a}^{m-a}$$\n($0^0=1$)。\n\n- $k=5$: $1\cdot 1=1$\n- $k=4$ ($m=1$): $a=1$ で $4$。$\left(\genfrac{}{}{0ex}{}{5}{4}\right)\cdot 4=20$\n- $k=3$ ($m=2$): $a=2$: $9$、$a=1$: $2\cdot 3\cdot 1=6$。計 $15$。$\left(\genfrac{}{}{0ex}{}{5}{3}\right)\cdot 15=150$\n- $k=2$ ($m=3$): $a=3$: $8$、$a=2$: $3\cdot 4\cdot 2=24$、$a=1$: $3\cdot 2\cdot 1=6$。計 $38$。$\left(\genfrac{}{}{0ex}{}{5}{2}\right)\cdot 38=380$\n- $k=1$ ($m=4$): $a=4$: $1$、$a=3$: $4\cdot 1\cdot 3=12$、$a=2$: $6\cdot 1\cdot 4=24$、$a=1$: $4\cdot 1\cdot 1=4$。計 $41$。$\left(\genfrac{}{}{0ex}{}{5}{1}\right)\cdot 41=205$\n\n合計 $1+20+150+380+205=756$。\n\n検算: 同じ式を $|A|=2$ に適用すると $1+2\cdot 1=3$ で、4 個の写像のうち互換 (入れ替え) のみが条件を満たさず 3 個、と一致する。