2019年入試問題研究に戻る

名大理系第4問

正の整数 $ n $ に対して $ 1,\ 2,\ \cdots,\ n $ を一列に並べた順列を考える. そのような順列は $ n! $ 個ある.このうちlつを等確率で選んだものを $ (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)  $ 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 $
となり,どの $ i $ から始めても列は必ず一巡する.この一巡するそれぞれの列をサイクル, 列に現れる相異なる整数の個数をサイクルの長さと呼ぶ. 上の(i),(ii),(iii)は長さがそれぞれ4,2,1のサイクルになっている.

(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 $ をみたすことを示せ.

解答