4名古屋大学 2019年 数学 第4問解答・解説

(1) 長さ $1$ のサイクルは、ある $i$ について $a_i=i$ となること、すなわち固定点があることを意味する。$n=3$ の全順列は $3!=6$ 個である。固定点をもたない順列は、$1\to2\to3\to1$ または $1\to3\to2\to1$ の二つだけである。したがって求める確率は $$\displaystyle 1-\frac{2}{6}=\boxed{\frac{2}{3}}.$$

(2) 長さ $4$ のサイクルでは、巡回の始点を $1$ と定めると、残りの並べ方は $2,3,4$ の $3!$ 通りである。対応する順列 $(a_1,a_2,a_3,a_4)$ は $$\boxed{(2,3,4,1),\ (2,4,1,3),\ (3,4,2,1),\ (3,1,4,2),\ (4,3,1,2),\ (4,1,2,3)}.$$ いずれも $1$ から始めて全ての数字を一度ずつ通って $1$ に戻るサイクルであり、始点を $1$ とした表し方は重複しないので、これですべてである。

(3) $j\le x<j+1$ では $1/x\le 1/j$ で、$j<x<j+1$ では不等号が厳しい。よって $$\displaystyle \int_j^{j+1}\frac{dx}{x}<\frac{1}{j}.$$ これを $j=k,k+1,\ldots,n$ について加えると $$\displaystyle \log(n+1)-\log k =\int_k^{n+1}\frac{dx}{x} =\sum\limits _{j=k}^{n}\int_j^{j+1}\frac{dx}{x} <\sum\limits _{j=k}^{n}\frac{1}{j},$$ となり、示された。

(4) $m=(n+1)/2$ とおく。長さ $r$ のサイクルを一つ含む順列の個数は、サイクルに入る $r$ 個の数字の選び方 $\displaystyle \binom nr$、その数字でサイクルを作る方法 $(r-1)!$、残りの数字の並べ方 $(n-r)!$ を掛けて $$\displaystyle \binom nr(r-1)!(n-r)!=\frac{n!}{r}$$ 個である。したがって、長さ $r$ のサイクルを含む確率は $1/r$ である。

長さが $m$ 以上のサイクルが二つあると、その長さの和は少なくとも $2m=n+1$ となって数字が足りない。ゆえに該当するサイクルは高々一つであり、異なる長さごとの事象は互いに重ならない。したがって $$\displaystyle p=\sum\limits _{r=m}^{n}\frac{1}{r}.$$ (3)を $k=m$ に適用すると $$\displaystyle p>\log(n+1)-\log m =\log\frac{n+1}{(n+1)/2} =\boxed{\log 2}.$$ よって求める不等式が成り立つ。