独自の解答・詳解
問題文は非掲載
小問4問・無料

名古屋大学　2019年度　前期日程　理科系

第4問場合の数の解答・解説

順列のサイクル・かく乱順列・対数と調和級数・積分による評価当サイトの体感難易度：難最終更新 2026/10/12

問題文について

大学の公式解答ではなく、当サイト独自の解答・解説です。問題文は掲載していません。理科系の問題文は、この年度については大学が公開していません（2026/10/12時点）。お手元の過去問集・赤本などでご確認ください。

問題を転載している非公式サイトへのリンクは、当サイトでは行っていません。

(1) $1, 2, \dots, n$ の順列 $(a_{1}, \dots, a_{n})$ を等確率に選び、 $a_{i} = j \to a_{j} = k \to \dots$ とたどってできる巡回の長さをサイクルの長さとする。 $n = 3$ のとき、選んだ順列が長さ $1$ のサイクルを含む確率を求める

答 $\frac{2}{3}$

長さ $1$ のサイクルとは $a_{i} = i$ （不動点）のこと。余事象は「不動点がない」、つまりかく乱順列である。 $n = 3$ なら数えるだけで済む。

長さ $1$ のサイクルは $a_{i} = i$ となる $i$ そのものである（ $a_{i} = i$ なら1歩で戻る）。

$n = 3$ の順列は $3! = 6$ 通りで、 $a_{i} = i$ となる $i$ が1つもないのは

(2, 3, 1), (3, 1, 2)

の $2$ 通りである（どちらも長さ $3$ のサイクル1つ）。よって長さ $1$ のサイクルを含むのは $6 - 2 = 4$ 通りで、求める確率は

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

である。

残り4通りを書き出すと $(1, 2, 3)$ （長さ1が3つ）、 $(1, 3, 2), (3, 2, 1), (2, 1, 3)$ （長さ1が1つと長さ2が1つ）である。

$6$ 通りを全列挙して数えると $4$ 通りだった。

(2) $n = 4$ のとき、長さ $4$ のサイクルを含む順列をすべて挙げる

答 $(2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 3, 1, 2)$ の6個

長さ $4$ のサイクルは $1, 2, 3, 4$ をひと回りする巡回で、 $1$ から出発して残り3つを並べる順番で決まるから $3! = 6$ 個。巡回の順番を書き出し、それを $a_{i}$ の形に直す。

$n = 4$ で長さ $4$ のサイクルを含むのは、 $1, 2, 3, 4$ 全体が1つの巡回になっているときである。巡回は $1 \to x \to y \to z \to 1$ の形で、 $(x, y, z)$ は $2, 3, 4$ の並べ方だから $3! = 6$ 通りある。

それぞれを $(a_{1}, a_{2}, a_{3}, a_{4})$ に直す。たとえば $1 \to 2 \to 3 \to 4 \to 1$ なら $a_{1} = 2, a_{2} = 3, a_{3} = 4, a_{4} = 1$ である。

$1 \to 2 \to 3 \to 4 \to 1$ ： $(2, 3, 4, 1)$
$1 \to 2 \to 4 \to 3 \to 1$ ： $(2, 4, 1, 3)$
$1 \to 3 \to 2 \to 4 \to 1$ ： $(3, 4, 2, 1)$
$1 \to 3 \to 4 \to 2 \to 1$ ： $(3, 1, 4, 2)$
$1 \to 4 \to 2 \to 3 \to 1$ ： $(4, 3, 1, 2)$
$1 \to 4 \to 3 \to 2 \to 1$ ： $(4, 1, 2, 3)$

番号順に並べ直すと

(2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 3, 1, 2)

の6個である。

$24$ 通りを全列挙してサイクル分解すると、長さ $4$ のサイクル1つになるのはこの6通りだけだった。

巡回の書き方 $1 \to 3 \to 2 \to 4 \to 1$ と、順列の書き方 $(3, 4, 2, 1)$ を混同しない。前者は「次にどこへ行くか」の並び、後者は添字順に値を並べたものである。

$(2, 1, 4, 3)$ のような「長さ2が2つ」は長さ4のサイクルではない。

(3) $n$ 以下の正の整数 $k$ に対して $j = k \sum n \frac{1}{j} > lo g (n + 1) - lo g k$ を示す

答 $\frac{1}{j} > \int_{j}^{j + 1} \frac{d x}{x}$ を $j = k$ から $n$ まで足す

$\frac{1}{x}$ は減少関数なので、区間 $[j, j + 1]$ では $\frac{1}{x} ≦ \frac{1}{j}$ で、等号は左端だけ。幅 $1$ の区間で積分すると $\frac{1}{j}$ のほうが真に大きい。これを足し合わせると右辺の $lo g$ が望遠鏡のように縮む。

$j$ を正の整数とする。 $j ≦ x ≦ j + 1$ では $\frac{1}{x} ≦ \frac{1}{j}$ で、 $x > j$ では真に $\frac{1}{x} < \frac{1}{j}$ である。よって

\int_{j}^{j + 1} \frac{d x}{x} < \int_{j}^{j + 1} \frac{d x}{j} = \frac{1}{j}

である。左辺は

\int_{j}^{j + 1} \frac{d x}{x} = lo g (j + 1) - lo g j

だから

\frac{1}{j} > lo g (j + 1) - lo g j

である。これを $j = k, k + 1, \dots, n$ について足すと、右辺は隣どうしで打ち消し合って

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

となる。よって

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

である。 $■$

$1 ≦ k ≦ n ≦ 59$ のすべての組で数値的に確かめ、反例は $0$ 件だった。

不等号が真に成り立つことを言うには、 $\frac{1}{x} < \frac{1}{j}$ となる $x$ が区間の中に正の長さぶんあることに触れる。

$lo g (n + 1)$ と $lo g n$ を取り違えない。区間の右端まで積分するので $n + 1$ である。

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

答長さがちょうど $L (L > \frac{n}{2})$ のサイクルをもつ確率が $\frac{1}{L}$ なので $p = L = \frac{n + 1}{2} \sum n \frac{1}{L} > lo g (n + 1) - lo g \frac{n + 1}{2} = lo g 2$

$L > \frac{n}{2}$ の長さのサイクルは、あったとしても1つしかない。だから「長さ $L$ のサイクルをもつ順列」の個数を数えて足せばよく、重複を心配しなくてよい。個数を数えると $\frac{n !}{L}$ というきれいな形になり、確率は $\frac{1}{L}$ になる。

長さが半分を超えるサイクルは高々1つ。 長さ $L_{1}, L_{2}$ の異なる2つのサイクルがあれば、それらは共通の数字をもたないので $L_{1} + L_{2} ≦ n$ である。 $L > \frac{n}{2}$ のサイクルが2つあると $L_{1} + L_{2} > n$ となって矛盾する。よって長さ $\frac{n}{2}$ より大きいサイクルは、あっても1つである。

$n$ は奇数なので $\frac{n + 1}{2} > \frac{n}{2}$ である。したがって「長さ $\frac{n + 1}{2}$ 以上のサイクルを含む」という事象は、 $L = \frac{n + 1}{2}, \frac{n + 1}{2} + 1, \dots, n$ について「長さがちょうど $L$ のサイクルをもつ」という事象の排反な和になる。

長さちょうど $L$ のサイクルをもつ順列の個数。 $\frac{n}{2} < L ≦ n$ とする。

サイクルに入る $L$ 個の数字を選ぶ： $_{n} C_{L}$ 通り
その $L$ 個を1つの巡回に並べる： $(L - 1)!$ 通り（円順列）
残り $n - L$ 個の並べ方： $(n - L)!$ 通り（ $n - L < \frac{n}{2} < L$ なので、ここから長さ $L$ 以上のサイクルは出てこない）

よって個数は

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

である。全体が $n!$ 通りなので、長さちょうど $L$ のサイクルをもつ確率は $\frac{1}{L}$ である。

$p$ を書く。 排反な和だから

p = L = \frac{n + 1}{2} \sum n \frac{1}{L}

である。(3) を $k = \frac{n + 1}{2}$ （ $n$ が奇数なので正の整数）として使うと

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

である。 $■$

$n = 5$ なら $p = \frac{1}{3} + \frac{1}{4} + \frac{1}{5} = \frac{47}{60} = 0.7833$ 、 $n = 11$ なら $0.7365$ で、 $n$ を大きくしても $lo g 2 = 0.6931$ を下回らない。実際 $n \to \infty$ で $p \to lo g 2$ に近づく。

$n = 5, 7, 9, 11$ で全順列を列挙して $p$ を分数で求めると、 $\frac{47}{60}, \frac{319}{420}, \frac{1879}{2520}, \frac{20417}{27720}$ となり、 $\sum_{L} \frac{1}{L}$ と完全に一致した。いずれも $lo g 2 = 0.69314718$ より大きい。

「長さ $\frac{n + 1}{2}$ 以上」をいきなり足すと重複を疑いたくなるが、半分を超える長さのサイクルは高々1つなので排反である。 $n$ が奇数という条件はここで効く。

$_{n} C_{L} (L - 1)! (n - L)! = \frac{n !}{L}$ の約分を丁寧に書く。 $L!$ と $(L - 1)!$ が $L$ だけ残す。

(3) の $k$ に $\frac{n + 1}{2}$ を入れるには、それが正の整数で $k ≦ n$ であることが要る。 $n$ が奇数で $n ≧ 1$ ならどちらも成り立つ。

2019年度の全4問をまとめて読む

大学の公式解答ではなく、当サイト独自の解答・解説です。問題文は掲載していません。解答は当サイトで検算していますが、誤りが残っている可能性はあります。掲載方針

当サイト運営者が制作した教材

同じ形式の問題を、5回分

合格答案をつくる名大数学2027

名大理系数学の出題を分析して書き下ろした予想問題集です。過去問そのものは入っていません。本番と同じ試験時間・大問構成で5回分、解答・詳解・別解に加えて、小問ごとの加点・減点つきの採点表を収録しています。

Amazonで見る全3巻を見る¥2,695・124ページ・2026年7月23日発売

中身を試し読みする

扉・問題・解答などを、それぞれ抜粋して掲載しています。連続したページではありません。画像を押すと拡大できます。

抜粋をPDFでまとめて見る

問題文について

(1)1,2,…,n の順列 (a1​,…,an​) を等確率に選び、ai​=j→aj​=k→⋯ とたどってできる巡回の長さをサイクルの長さとする。n=3 のとき、選んだ順列が長さ 1 のサイクルを含む確率を求める

(2)n=4 のとき、長さ 4 のサイクルを含む順列をすべて挙げる

(3)n 以下の正の整数 k に対して j=k∑n​j1​>log(n+1)−logk を示す

(4)n を奇数とするとき、選んだ順列が長さ 2n+1​ 以上のサイクルを含む確率 p が p>log2 を満たすことを示す