5大阪医科薬科大学 2022年 数学 第5問解答・解説

〔5〕

(1)
順列を $\sigma(i)=x_i$ とみなす。点集合が $y=x$ に関して線対称であることは、各点 $(i,x_i)$ の反射 $(x_i,i)$ も集合に属することと同値である。第1座標が $x_i$ である点は $(x_i,x_{x_i})$ だから、これは $x_{x_i}=i$、すなわち $\sigma(\sigma(i))=i$ が全ての $i$ で成立することと同値である。従って対象は互換と固定点だけからなる順列である。
$n$ の行き先で場合分けする。$\sigma(n)=n$ なら残りは $n-1$ 個の対象上の対称な順列で $a_{n-1}$ 通り。$\sigma(n)\ne n$ なら相手 $j=\sigma(n)$ を $n-1$ 通りから選ぶと、$\sigma(j)=n$ と定まり、残り $n-2$ 個は自由な対称な順列となる。よって（$n\geqq3$）
$$\boxed{a_n=a_{n-1}+(n-1)a_{n-2}}.$$
空集合の順列を $a_0=1$ と数えれば、この式は $n=2$ にも成り立つ。
(2)
漸化式を法3で用いると
$$a_{3k+1}=a_{3k}+3k\,a_{3k-1}\equiv a_{3k}\pmod3.$$
さらに
$$a_{3k+2}=a_{3k+1}+(3k+1)a_{3k} \equiv a_{3k+1}+a_{3k} \equiv2a_{3k}\pmod3.$$
従って二つの合同式が成り立つ。
(3)
まず $a_3=a_2+2a_1=4\equiv1\pmod3$。$k\geqq2$ とし、問(2)を $k-1$ に適用すると
$$a_{3k-1}=a_{3(k-1)+2}\equiv2a_{3k-3},\qquad a_{3k-2}=a_{3(k-1)+1}\equiv a_{3k-3}\pmod3.$$
よって
$$a_{3k}=a_{3k-1}+(3k-1)a_{3k-2} \equiv a_{3k-1}-a_{3k-2} \equiv a_{3k-3}\pmod3.$$
帰納的に全ての $k\geqq1$ で $a_{3k}\equiv a_3\equiv1\pmod3$。問(2)から $a_{3k+1}\equiv1$、$a_{3k+2}\equiv2\pmod3$ であり、初項 $a_1=1,a_2=2$ も同じ剰余である。従って全ての自然数 $n$ について
$$\boxed{a_n\not\equiv0\pmod3}.$$
検算
$n=1,2,3$ では $a_1=1,a_2=2,a_3=4$ で剰余は1,2,1。漸化式から3項ごとの剰余が1,1,2の並びで繰り返すことが示され、結論と一致する。