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

問題

正の整数 $n$ に対して $1, 2, \dots, n$ を一列に並べた順列を考える。そのような順列は $n!$ 個ある。このうち1つを等確率で選んだものを $(a_{1}, a_{2}, \dots, a_{n})$ とする。この $(a_{1}, a_{2}, \dots, a_{n})$ に対し，各添字 $i = 1, 2, \dots, 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 \to \dots$ のようにたどり，それを続けていく。例えば $(a_{1}, 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$ に対して

j = k \sum n \frac{1}{j} > lo g (n + 1) - lo g k

を示せ。

(4) $n$ を奇数とする。選んだ順列が長さ $\frac{n + 1}{2}$ 以上のサイクルを含む確率 $p$ は $p > lo g 2$ をみたすことを示せ。

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

方針

順列を写像 $i \mapsto a_{i}$ と見てサイクル分解で数える。(1)は $n = 3$ の全6通りから、長さ1のサイクルをもたない3サイクル2通りを引く。(2)は $1$ から始まる4サイクル $(1, *, *, *)$ をすべて書き、それを一列表示 $(a_{1}, a_{2}, a_{3}, a_{4})$ に直す。(3)は $1/ x$ が減少することから、各区間 $[j, j + 1]$ の積分を $1/ j$ より小さく押さえる。(4)は長さ $j$ のサイクルを含む順列の個数が $n! / j$ であることを数え、 $j > (n /2)$ の長いサイクルは同時に2つ存在しないため確率を足し合わせられることを使う。最後に(3)を $k = (n + 1) /2$ に適用する。

解答

(1)

$n = 3$ の順列は全部で $3! = 6$ 通りである。長さ1のサイクルを含まない順列は、3つの数すべてが1つのサイクルになる場合である。これは $(123), (132)$ の2通りである。

したがって、長さ1のサイクルを含む順列は $6 - 2 = 4$ 通りであり、求める確率は $\frac{4}{6} = \frac{2}{3}$ である。

(2)

長さ4のサイクルを含むということは、4つの数すべてが1つのサイクルに入るということである。1から始めて書けば、4サイクルは $(1234), (1243), (1324),$ $(1342), (1423), (1432)$ の6通りである。これを一列表示 $(a_{1}, a_{2}, a_{3}, a_{4})$ に直すと $(2, 3, 4, 1), (2, 4, 1, 3), (3, 4, 2, 1),$ $(3, 1, 4, 2), (4, 3, 1, 2), (4, 1, 2, 3)$ である。

(3)

$j ≦ x ≦ j + 1$ では $\frac{1}{x} ≦ \frac{1}{j}$ であり、区間全体で等号が成り立つわけではない。したがって $\int_{j}^{j + 1} \frac{d x}{x} < \frac{1}{j}$ である。これを $j = k, k + 1, \dots, n$ について足すと $\int_{k}^{n + 1} \frac{d x}{x} < \sum_{j = k}^{n} \frac{1}{j}$ である。左辺は $lo g (n + 1) - lo g k$ だから $j = k \sum n \frac{1}{j} > lo g (n + 1) - lo g k$ が示された。

(4)

長さ $j$ のサイクルを含む順列の個数を数える。まず、そのサイクルに入る $j$ 個の数を選ぶ方法は $_{n} C_{j}$ 通りである。選んだ $j$ 個で長さ $j$ のサイクルを作る方法は $(j - 1)!$ 通りである。残り $n - j$ 個の並び方は任意なので $(n - j)!$ 通りである。よって個数は $_{n} C_{j} (j - 1)! (n - j)! = \frac{n !}{j}$ であり、確率は $1/ j$ である。

いま $n$ は奇数であり、 $j ≧ \frac{n + 1}{2}$ とする。このような長さのサイクルが2つ同時に存在すると、長さの和が少なくとも $\frac{n + 1}{2} + \frac{n + 1}{2} = n + 1$ となり、 $n$ 個の文字数を超えてしまう。したがって、長さ $\frac{n + 1}{2}$ 以上のサイクルを含む事象は、長さ $j$ ごとに互いに排反である。

よって求める確率 $p$ は $p = \sum_{j = (n + 1) /2}^{n} \frac{1}{j}$ である。(3)を $k = \frac{n + 1}{2}$ として用いると $p > lo g (n + 1) - lo g \frac{n + 1}{2} = lo g 2$ である。したがって $p > lo g 2$ が示された。

名古屋大学 2019年度理系数学 第4問

問題

方針

解答

(1)

(2)

(3)

(4)

名古屋大学 2019年度
理系数学第4問