2019年入試問題研究に戻る名大理系第4問解答
(1) $ n=3 $ のとき，長さ1のサイクルを含む順列は， $ a_i=i $ となる項がある順列なので， \[ (1,\ 2,\ 3),\ (1,\ 3,\ 2),\ (3,\ 2,\ 1),\ (2,\ 1,\ 3) \] の4個ある．よってその確率は $ \dfrac{4}{3!}=\dfrac{2}{3} $ である． 長さ3のサイクルがあるものは $ 6-4=2 $ 個である．
(2) $ 1,\ 2,\ \cdots,\ n $ を一列に並べた順列のうち，長さ $ n $ のサイクルである順列の個数を $ x_n $ とおく．
長さ $ n $ のサイクルがあるとき，新たに $ a_{n+1} $ を加えて長さ $ n+1 $ のサイクルを構成する方法は， $ a_i=n+1,\ a_{n+1}=a_i\ (1\leqq i \leqq n) $ と， $ n $ 通りある． よって， \[ x_{n+1}=nx_n \] がなりたつ． $ x_1=1 $ なので， $ x_n=(n-1)! $ である．
$ x_4=3!=6 $ である．長さ3のサイクルがあるものは(1)より， $ 6-4=2 $ 個である．それは $ (2,\ 3,\ 1) $ ， $ (3,\ 1,\ 2) $ である．これをもとに上記の手順で $ x_4 $ 個の順列を作ると， \[ \begin{array}{l} (4,3,1,2),\ (2,4,1,3),\ (2,3,4,1),\ \\ (4,1,2,3),\ (3,4,2,1),\ (3,1,4,2) \end{array} \] である．
※ $ x_n $ は次のようにしても求まる．
サイクルはどこからはじめても同じサイクルなので，長さ $ n $ のサイクルである順列は， \[ a_1=k_1,\ a_{k_1}=k_2,\ \cdots,\ a_{k_{n-2}}=k_{n-1},\ a_{k_{n-1}}=1 \] と， $ k_1,\ k_2,\ \cdots,\ k_{n-1} $ に $ 2,\ 3,\ \cdots,\ n $ をあてはめるだけある． よって， $ x_n=(n-1)! $ である．
(3) 正の実数で定義された関数 $ \dfrac{1}{x} $ は単調減少であるから， 区間 $ (j,\ j+1] $ で $ \dfrac{1}{j} >\dfrac{1}{x} $ がなりたつ． よって， \[ \int_j^{j+1}\dfrac{1}{j}\,dx >\int_j^{j+1}\dfrac{1}{x}\,dx \] つまり， \[ \dfrac{1}{j} >\log(j+1)-\log j \] である．これを $ k\leqq p\leqq n $ で加えて， \[ \sum_{j=k}^n\dfrac{1}{j} >\sum_{j=k}^n\left\{\log(j+1)-\log j \right\}=\log(n+1)-\log k \] である．
(4) $ j\geqq \dfrac{n+1}{2} $ とする．長さ $ j $ のサイクルは存在しても1個である． それを構成する項を $ a_l,a_2,\cdots,a_n $ から選ぶ．それは $ {}_n \mathrm{C}_j $ 通りある． それを用いて長さ $ j $ のサイクルを作る．それは $ (j-1)! $ 通りある．
残る $ n-j $ は任意であり， $ (n-j)! $ 通りある．よって， 長さ $ j $ のサイクルが存在する場合の数は \[ {}_n \mathrm{C}_j\cdot(j-1)!\cdot(n-j)!=\dfrac{n!}{j!(n-j)!}\cdot(j-1)!\cdot(n-j)!=\dfrac{n!}{j} \] 通りある．よって，長さ $ j $ のサイクルが存在する確率は $ \dfrac{1}{j} $ である． これより， 選んだ順列が長さ $ \dfrac{n+1}{2} $ 以上のサイクルを含む確率 $ p $ は(3)を用いて， \[ \sum_{j=\frac{n+1}{2}}^n\dfrac{1}{j} >\log(n+1)-\log \dfrac{n+1}{2}=\log 2 \] である．