2019年入試問題研究に戻る名大理系第4問
正の整数 $ n $ に対して $ 1,\ 2,\ \cdots,\ n $ を一列に並べた順列を考える． そのような順列は $ n! $ 個ある．このうちｌつを等確率で選んだものを $ (a_l,a_2,\cdots,a_n) $ とする．この $ (a_l,a_2,\cdots,a_n) $ に対し， 各添字 $ i=1,\ 2,\ \cdots,\ n $ について， $ a_i $ の値が $ j $ であるとき，その $ j $ を添字にもつ $ a_j $ の値が $ k $ であることを $ a_i=j\to a_j=k $ と書くことにする．ここで $ a_i=j\to a_j=k\to a_k=l $ のようにたどり， それを続けていく．例えば $ (a_l,a_2,a_3,a_4,a_5,a_6,a_7)=(2,\ 5,\ 6,\ 1,\ 4,\ 3,\ 7) $ のとき，
となり，どの $ i $ から始めても列は必ず一巡する．この一巡するそれぞれの列をサイクル， 列に現れる相異なる整数の個数をサイクルの長さと呼ぶ． 上の(i)，(ii)，(iii)は長さがそれぞれ4，2，1のサイクルになっている．(i) $ a_1=2\to a_2=5\to a_5=4\to a_4=1\to a_1=2 $
(ii) $ a_3=6\to a_6=3\to a_3=6 $
(iii) $ a_7=7\to a_7=7 $
(1) $ n=3 $ とする．選んだ順列が長さ1のサイクルを含む確率を求めよ．
(2) $ n=4 $ とする．長さ4のサイクルを含む順列をすべて拳げよ．
(3) $ n $ 以下の正の整数 $ k $ に対して \[ \sum_{j=k}^n\dfrac{1}{j}>\log(n+1)-\log k \] を示せ．
(4) $ n $ を奇数とする．選んだ順列が長さ $ \dfrac{n+1}{2} $ 以上のサイクルを含む確率 $ p $ は $ p>\log 2 $ をみたすことを示せ．