名古屋大学 2019年度 前期日程 第2次学力試験理系数学 第4問

(1)
$n=3$ の順列は全部で$$3!=6$$通りである。長さ1のサイクルを含まない順列は、3つの数が1つのサイクルになる$$(123),(132)$$の2通りである。したがって求める確率は$$\frac{6-2}{6}=\frac{2}{3}$$である。

(2)
4つの数すべてを含むサイクルは、先頭を1に固定して$$\begin{array}{c}{\displaystyle (1234),(1243),(1324),}\\ {\displaystyle (1342),(1423),(1432)}\end{array}$$の6通りである。一列表示に直すと$$\begin{array}{c}{\displaystyle (2,3,4,1),(2,4,1,3),(3,4,2,1),}\\ {\displaystyle (3,1,4,2),(4,3,1,2),(4,1,2,3)}\end{array}$$である。

(3)
$j\leqq x\leqq j+1$ では$$\frac{1}{x}\leqq \frac{1}{j}$$であり、区間全体で等号が成り立つわけではない。したがって$${\int }_j^{j+1}\frac{dx}{x}<\frac{1}{j}\mathrm{.}$$これを $j=k,k+1,\dots ,n$ について加えると$$\begin{array}{rl}{\displaystyle \log (n+1)-\log k}& {\displaystyle ={\int }_k^{n+1}\frac{dx}{x}}\\ {\displaystyle }& {\displaystyle <\sum _{j=k}^n\frac{1}{j}\mathrm{.}}\end{array}$$よって$$\sum _{j=k}^n\frac{1}{j}>\log (n+1)-\log k$$が示された。

(4)
長さ $j$ のサイクルを含む順列を数える。サイクルに入る $j$ 個の数の選び方、選んだ数でサイクルを作る方法、残りを並べる方法はそれぞれ$${}_n{\mathrm{C}}_j,(j-1)!,(n-j)!$$通りである。したがって順列の個数は$${}_n{\mathrm{C}}_j(j-1)!(n-j)!=\frac{n!}{j}$$であり、その確率は$$\frac{1}{j}$$である。

$n$ は奇数で$$j\geqq \frac{n+1}{2}$$だから、この範囲の長さのサイクルが2つ同時に存在することはない。また異なる長さの事象どうしも排反である。よって$$p=\sum _{j=(n+1)\mathrm{/}2}^n\frac{1}{j}\mathrm{.}$$(3)で$$k=\frac{n+1}{2}$$とすれば$$\begin{array}{rl}{\displaystyle p}& {\displaystyle >\log (n+1)-\log \frac{n+1}{2}}\\ {\displaystyle }& {\displaystyle =\log 2.}\end{array}$$したがって$$p>\log 2$$が示された。

(1) は固定点をもつ事象を包除原理で数える。(3)は $\log (1+u)<u$ を微分で証明し、対数の差を和に分解する。(4)は長いサイクルを1つ指定して数えることで、同じ調和和へ帰着する。

(1)
各 $i=1,2,3$ に対して、$a_i=i$ となる事象を $A_i$ とする。包除原理により、固定点を少なくとも1つもつ順列の個数は$$3\cdot 2!-{}_3{\mathrm{C}}_2\cdot 1!+1=6-3+1=4.$$したがって確率は$$\frac{4}{3!}=\frac{2}{3}\mathrm{.}$$(2)
長さ4のサイクルでは、1の次、その次、その次に現れる3数を順に選べばよい。その並べ方は $3!=6$ 通りであり、一列表示は$$\begin{array}{c}{\displaystyle (2,3,4,1),(2,4,1,3),(3,4,2,1),}\\ {\displaystyle (3,1,4,2),(4,3,1,2),(4,1,2,3)}\end{array}$$となる。

(3)
$u>0$ に対して$$h(u)=u-\log (1+u)$$とおくと$$h^{\mathrm{\prime }}(u)=1-\frac{1}{1+u}=\frac{u}{1+u}>0,h(0)=0.$$よって$$\log (1+u)<u$$である。ここで$$u=\frac{1}{j}$$とすると$$\log \frac{j+1}{j}<\frac{1}{j}\mathrm{.}$$$j=k,k+1,\dots ,n$ について加えれば$$\begin{array}{rl}{\displaystyle \log (n+1)-\log k}& {\displaystyle =\sum _{j=k}^n\log \frac{j+1}{j}}\\ {\displaystyle }& {\displaystyle <\sum _{j=k}^n\frac{1}{j}\mathrm{.}}\end{array}$$これで示された。

(4)
$j\geqq (n+1)\mathrm{/}2$ を固定する。長さ $j$ のサイクルを1つ指定した順列の個数は$${}_n{\mathrm{C}}_j(j-1)!(n-j)!=\frac{n!}{j}\mathrm{.}$$この範囲では2つの長いサイクルが共存しないので、各順列はどの $j$ に対しても重複して数えられない。したがって$$p=\frac{1}{n!}\sum _{j=(n+1)\mathrm{/}2}^n\frac{n!}{j}=\sum _{j=(n+1)\mathrm{/}2}^n\frac{1}{j}\mathrm{.}$$(3)を適用すると$$p>\log (n+1)-\log \frac{n+1}{2}=\log 2.$$