名古屋大学 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問

方針

解法1

順列を写像 $i \mapsto a_{i}$ と見てサイクル分解する。(1)(2)は小さい順列を直接数え、(3)は減少関数 $1/ x$ のグラフと長方形の面積を比較する。(4)は長さ $j$ のサイクルを含む順列を数え、 $j > n /2$ の事象が互いに排反であることを使う。

解法2

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

解答

解法1

(1)

$n = 3$ の順列は全部で

3! = 6

通りである。長さ1のサイクルを含まない順列は、3つの数が1つのサイクルになる

(123), (132)

の2通りである。したがって求める確率は

\frac{6 - 2}{6} = \frac{2}{3}

である。

(2)

4つの数すべてを含むサイクルは、先頭を1に固定して

(1234), (1243), (1324), (1342), (1423), (1432)

の6通りである。一列表示に直すと

(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$ について加えると

lo g (n + 1) - lo g k = \int_{k}^{n + 1} \frac{d x}{x} < j = k \sum n \frac{1}{j} .

よって

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

が示された。

(4)

長さ $j$ のサイクルを含む順列を数える。サイクルに入る $j$ 個の数の選び方、選んだ数でサイクルを作る方法、残りを並べる方法はそれぞれ

_{n} C_{j}, (j - 1)!, (n - j)!

通りである。したがって順列の個数は

_{n} C_{j} (j - 1)! (n - j)! = \frac{n !}{j}

であり、その確率は

\frac{1}{j}

である。

$n$ は奇数で

j ≧ \frac{n + 1}{2}

だから、この範囲の長さのサイクルが2つ同時に存在することはない。また異なる長さの事象どうしも排反である。よって

p = j = (n + 1) /2 \sum 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

が示された。

解法2

(1)

各 $i = 1, 2, 3$ に対して、 $a_{i} = i$ となる事象を $A_{i}$ とする。包除原理により、固定点を少なくとも1つもつ順列の個数は

3 \cdot 2! -_{3} C_{2} \cdot 1! + 1 = 6 - 3 + 1 = 4.

したがって確率は

\frac{4}{3 !} = \frac{2}{3} .

(2)

長さ4のサイクルでは、1の次、その次、その次に現れる3数を順に選べばよい。その並べ方は $3! = 6$ 通りであり、一列表示は

(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)

$u > 0$ に対して

h (u) = u - lo g (1 + u)

とおくと

h^{'} (u) = 1 - \frac{1}{1 + u} = \frac{u}{1 + u} > 0, h (0) = 0.

よって

lo g (1 + u) < u

である。ここで

u = \frac{1}{j}

とすると

lo g \frac{j + 1}{j} < \frac{1}{j} .

$j = k, k + 1, \dots, n$ について加えれば

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

これで示された。

(4)

$j ≧ (n + 1) /2$ を固定する。長さ $j$ のサイクルを1つ指定した順列の個数は

_{n} C_{j} (j - 1)! (n - j)! = \frac{n !}{j} .

この範囲では2つの長いサイクルが共存しないので、各順列はどの $j$ に対しても重複して数えられない。したがって

p = \frac{1}{n !} j = (n + 1) /2 \sum n \frac{n !}{j} = j = (n + 1) /2 \sum n \frac{1}{j} .

(3)を適用すると

p > lo g (n + 1) - lo g \frac{n + 1}{2} = lo g 2.

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

問題

方針

解法1

解法2

解答

解法1

(1)

(2)

(3)

(4)

解法2

(1)

(2)

(3)

(4)

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