NF杯2023(K)

　条件より$f$は全射，ゆえに全単射である．

　$n$に対し, $f^{d_n}(n) = n$を満たす最小の正の整数 $d_n$ がある．これを $n$ の周期と呼ぶことにする．条件より周期 $d_n$ は $n$ の約数である． ここで非負整数 $i,j$ に対し，単射性から 　$$f^{j}(f^{i}(n)) = f^{i}(n) \iff f^{j}(n) = n \iff d_n \mid j$$ なので，$n,f(n),\dots, f^{d_n -1}(n)$の周期もまた $d_n$ となる．$0\leq i \lt d_n$とし， $a = f^{i}(n)$とおくと，$f^{a}(a) = a$ かつ $a$ の周期は $d_n$ なので，周期の最小性から $a$ が $d_n$ の倍数でなければならない．$a\in \{ 1,2,\dots, 13 \}$ なので，$1$ から $13$ までの整数の中に $d_n$ の倍数が $d_n$ 個以上あることになる．よって$d_n\cdot d_n \leq 13$ が従うから，$d_n = 1,2,3$でなければならない．これらと $d_n | n$ を考慮することで，特に次が分かる:

• $n$ が $2,3$と互いに素である場合( $n = 1,5,7,11,13$ )，$d_n = 1$，すなわち $f(n) = n$ でなければならない．よって $f$ は $8$元集合 $S = \{ 2,3,4,6,8,9,10,12 \}$ の置換で決まる．
• $n\in S$ が $3$ の倍数でない場合 ( $n = 2,4,8,10$ )，$d_n \neq 3$．
• $n\in S$ が 偶数でない場合 ( $n = 3,9$ )，$d_n \neq 2$．
• $n = 6, 12$ の場合，$d_n$ は $1,2,3$ のどの可能性もある．

　以降，$n\in S$ に対して $O_n$ は $n$ の$f$による軌道，すなわち集合 $\left\{ n, f(n), \dots, f^{d_n - 1(n)} \right\}$ を表すとする．$O_n$ の長さ (元の個数) は $d_n$ であり，集合 $S$ は $O_n$ ($n\in S$) のいくつかで分割される． この分割の可能性について考察する．

　まず，$S$ の分割に長さ $3$ の軌道は高々 $1$ つしか含まれない．実際，長さ $3$ の軌道に含まれる数は $3$ の倍数でなければならず，集合$S$ に 含まれる $3$ の倍数は $6$ 個未満であるからである．同様の議論で，$S$ に属す 偶数は $6$ 個なので，長さ $2$ の軌道は $3$ 個以下である.

　長さ $2,3$ の軌道の数をそれぞれ $x_2,x_3$ として，$(x_2,x_3)$ に関して場合分けすると以下のようになる．

• $(x_2,x_3) = (0,0)$ のとき，すべてが固定点なので $1$ 個．

• $(x_2,x_3) = (1,0)$ のとき，長さ $2$ の軌道に入るべき数は $2,4,6,8,10,12$ の $6$ 個なので ${}_{6}\mathrm{C}_{2} = 15$ 個．

• $(x_2,x_3) = (0,1)$ のとき，長さ $3$ の軌道に入るべき数は $3,6,9,12$の4個であり，円順列を考えることで $\dfrac{{}_{4}\mathrm{P}_{3}}{3} = 8$個．

• $(x_2,x_3) = (2,0)$ のとき，$2,4,6,8,10,12$ から 4 つ選んで 2 つずつに分ける方法を考え，$\dfrac{{}_{6}\mathrm{C}_{4}\cdot {}_{4}\mathrm{C}_{2}}{2!} = 45$個．

• $(x_2,x_3) = (1,1)$ のとき，長さ$2, 3$の軌道をそれぞれ $S_2, S_3$ とする．$S_3$ には $6$ か $12$ の少なくとも一方が入っており，以下の3ケースに分けて考えることで，$24+20+20 = 64$個の$f$を得る．

  (Case 1.1.) $6,12\in S_3$ のとき, $S_3$としてありうるのは $12\mapsto 6 \mapsto i\mapsto 12$と$12\mapsto i\mapsto 6\mapsto 12$ ($i=3,9$) の4パターンである．$S_2$ は $2,4,8,10$ から2つの数字を選んで構成すればよいので, ${}_{4}\mathrm{C}_{2} = 6$パターンがある. よって24個の $f$ を得る．

  (Case 1.2.) $12\in S_3$ かつ $6\notin S_3$ のとき，$S_3$は $12\mapsto 3\mapsto 9$ か $12\mapsto 9\mapsto 3$ の2個. $S_2$は $2,4,6,8,10$ から2つの数字を選んで構成すればよいので ${}_{5}\mathrm{C}_{2} = 10$ 個．よって20個の$f$を得る．

  (Case 1.3.) $6\in S_3$ かつ $12\notin S_3$ のときも Case 1.2. と同様に同様に 20個．

• $(x_2,x_3) = (3,0)$ のとき，長さ2の軌道3つを $2,4,6,8,10,12$ から作る方法の個数だけ$f$が得られるので，$\dfrac{{}_{6}\mathrm{C}_{2}\cdot {}_{4}\mathrm{C}_{2}\cdot {}_{2}\mathrm{C}_{2}}{3!} = 15$個．

• $(x_2,x_3) = (2,1)$ のとき，以下のように$12 + 30 + 30 = 72$個の$f$を得る．唯一の長さ3の軌道を$S_3$とする．

  (Case 2.1.) $6,12 \in S_3$ のとき，Case 1.1と同様に 4通りの $S_3$ がある．長さ2の軌道2つの分け方は$2,4,8,10$ を二つに分ける方法だけあるので $\dfrac{{}_{4}\mathrm{C}_{2}}{2!} = 3$ 通り．よって12個の$f$を得る．　

  (Case 2.2.) $12\in S_3, 6\notin S_3$の場合，$S_3$は2通り( Case 1.2 と同様). 長さ2の軌道2つは$2,4,6,8,10$ を二つに分ける方法だけあるので, $\dfrac{{}_{5}\mathrm{C}_{2} \cdot {}_{3}\mathrm{C}_{2}}{2!} = 15$ 個. よって30個の $f$ を得る.

  (Case 2.3.) $6\in S_3,\quad 12\notin S_3$の場合，**Case 2.2.**と同様に30個得られる.

　以上より，求める $f$ の個数は $$1 + 15 + 8 + 45 + 64 + 15 + 72 = \mathbf{220}$$