トップ› 名古屋大学› 2019年› 理系第4問

名古屋大学 2019年理系第4問解説

方針・初手

順列を「サイクル（巡回置換）」に分解して考える問題である。 (1), (2) は定義に従って具体的に書き出して数え上げる。(3) は定積分を用いた級数の不等式評価の典型問題である。(4) は (3) の結果を利用することを見越して、指定された長さのサイクルを含む順列の個数を組合せ論的に求める。その際、サイクルの長さが半分を超えていることを用いて、事象が排反になることを利用する。

解法1

(1)

$n=3$ のとき、すべての順列 $(a_1, a_2, a_3)$ は $3! = 6$ 通りある。長さ1のサイクルを含むということは、$a_i = i$ となる $i$ ($1 \le i \le 3$) が少なくとも1つ存在することである。これを満たす順列をすべて書き出すと、

$a_1 = 1$ を満たすもの：$(1, 2, 3), (1, 3, 2)$
$a_2 = 2$ を満たすもの：$(1, 2, 3), (3, 2, 1)$
$a_3 = 3$ を満たすもの：$(1, 2, 3), (2, 1, 3)$

重複を除いて列挙すると、$(1, 2, 3), (1, 3, 2), (2, 1, 3), (3, 2, 1)$ の4通りである。よって、求める確率は

$$ \frac{4}{6} = \frac{2}{3} $$

(2)

$n=4$ のとき、長さ4のサイクルとなる順列は、$1, 2, 3, 4$ が1つのサイクルを作るものである。そのようなサイクルの総数は円順列の考え方を用いて $(4-1)! = 3! = 6$ 個ある。これらをすべて書き上げる。$a_1$ の値によって場合分けする。

$a_1 = 2$ のとき、サイクルが1周するために $a_2 \neq 1$ である。 $a_2 = 3$ とすると $a_3 = 4, a_4 = 1$。順列は $(2, 3, 4, 1)$。 $a_2 = 4$ とすると $a_4 = 3, a_3 = 1$。順列は $(2, 4, 1, 3)$。

$a_1 = 3$ のとき、$a_3 \neq 1$ である。 $a_3 = 2$ とすると $a_2 = 4, a_4 = 1$。順列は $(3, 4, 2, 1)$。 $a_3 = 4$ とすると $a_4 = 2, a_2 = 1$。順列は $(3, 1, 4, 2)$。

$a_1 = 4$ のとき、$a_4 \neq 1$ である。 $a_4 = 2$ とすると $a_2 = 3, a_3 = 1$。順列は $(4, 3, 1, 2)$。 $a_4 = 3$ とすると $a_3 = 2, a_2 = 1$。順列は $(4, 1, 2, 3)$。

よって、求める順列は以下の6つである。 $(2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 3, 1, 2)$

(3)

自然数 $j$ に対して、区間 $x \in (j, j+1)$ において関数 $y = \frac{1}{x}$ は単調減少であるから、

$$ \frac{1}{j} > \frac{1}{x} $$

が成り立つ。この両辺を $j$ から $j+1$ まで積分すると、

$$ \int_{j}^{j+1} \frac{1}{j} dx > \int_{j}^{j+1} \frac{1}{x} dx $$

左辺は $\frac{1}{j} (j+1 - j) = \frac{1}{j}$ であるから、

$$ \frac{1}{j} > \int_{j}^{j+1} \frac{1}{x} dx $$

この不等式の両辺について、$j=k, k+1, \dots, n$ の和をとると、

$$ \sum_{j=k}^{n} \frac{1}{j} > \sum_{j=k}^{n} \int_{j}^{j+1} \frac{1}{x} dx $$

右辺の積分は区間がつながるので、

$$ \begin{aligned} \sum_{j=k}^{n} \int_{j}^{j+1} \frac{1}{x} dx &= \int_{k}^{n+1} \frac{1}{x} dx \\ &= \Big[ \log x \Big]_{k}^{n+1} \\ &= \log(n+1) - \log k \end{aligned} $$

よって、

$$ \sum_{j=k}^{n} \frac{1}{j} > \log(n+1) - \log k $$

が示された。

(4)

$n$ 個の要素からなる順列において、長さ $m$ のサイクルを含む事象を考える。 $m \ge \frac{n+1}{2}$ のとき、$2m \ge n+1 > n$ となるため、1つの順列の中に長さ $m$ のサイクルは高々1つしか存在し得ない。また、異なる長さのサイクル（どちらも $\frac{n+1}{2}$ 以上）が同時に存在することも要素数が足りないため不可能である。したがって、長さが $\frac{n+1}{2}$ 以上となる各サイクルを含む事象はすべて排反である。

長さ $m$ のサイクルを含む順列の個数を求める。まず、$n$ 個の要素からサイクルを構成する $m$ 個を選ぶ方法は ${}_{n}\mathrm{C}_{m}$ 通り。選んだ $m$ 個の要素で1つのサイクルを作る方法は円順列より $(m-1)!$ 通り。残った $n-m$ 個の要素の並べ方は $(n-m)!$ 通り。以上より、長さ $m$ のサイクルを含む順列の個数は、

$$ {}_{n}\mathrm{C}_{m} \times (m-1)! \times (n-m)! = \frac{n!}{m!(n-m)!} (m-1)! (n-m)! = \frac{n!}{m} $$

事象は排反であるから、長さ $\frac{n+1}{2}$ 以上のサイクルを含む順列の総数は、各 $m$ ($m = \frac{n+1}{2}, \frac{n+3}{2}, \dots, n$) について足し合わせたものになる。よって、その確率 $p$ は、

$$ \begin{aligned} p &= \frac{1}{n!} \sum_{m=\frac{n+1}{2}}^{n} \frac{n!}{m} \\ &= \sum_{m=\frac{n+1}{2}}^{n} \frac{1}{m} \end{aligned} $$

ここで、(3) で示した不等式に $k = \frac{n+1}{2}$ を代入すると、

$$ \begin{aligned} \sum_{m=\frac{n+1}{2}}^{n} \frac{1}{m} &> \log(n+1) - \log\left(\frac{n+1}{2}\right) \\ &= \log(n+1) - (\log(n+1) - \log 2) \\ &= \log 2 \end{aligned} $$

したがって、

$$ p > \log 2 $$

が示された。

解説

順列をサイクルの積で表す（巡回置換への分解）という、群論や離散数学で扱われる概念を題材にした問題である。 (1), (2) でサイクルの意味を具体例を通して理解させ、(3) で評価用の中間不等式を準備し、(4) で確率を求めるという誘導になっている。 (4) において最も重要なポイントは、「指定された長さ $m$ が $\frac{n+1}{2}$ 以上であれば、1つの順列の中にそのようなサイクルは1つしか存在できない」という事実から、数え上げる事象が「排反」になることである。これにより、複雑な包除原理などを考えずに、単純な和の計算で確率を求めることができる。