Evolton

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

正の整数nに対して1, 2, ⋯ , nを一列に並べた順列を考える。
そのような順列はn !個ある。
このうち1つを等確率で選んだものを(a1, a2, ⋯ , an)とする。
この(a1, a2, ⋯ , an)に対し,
各添字i=1, 2, ⋯ , nについて,aiの値がjであるとき,
そのjを添字にもつajの値がkであることをai=j→aj=kと書くことにする。
ここでai=j→aj=k→ak=l→⋯のようにたどり,それを続けていく。
例えば(a1, a2, a3, a4, a5, a6, a7)=(2, 5, 6, 1, 4, 3, 7)のとき,

(i) a1=2→a2=5→a5=4→a4=1→a1=2

(ii) a3=6→a6=3→a3=6

(iii) a7=7→a7=7

となり,どのiから始めても列は必ず一巡する。この一巡するそれぞれの列をサイクル,
列に現れる相異なる整数の個数をサイクルの長さと呼ぶ。
上の(i),(ii),(iii)は長さがそれぞれ4,2,1のサイクルになっている。

(1) n=3とする。選んだ順列が長さ1のサイクルを含む確率を求めよ。

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

(3) n以下の正の整数kに対して∑j=kn1j>log⁡(n+1)−log⁡kを示せ。

(4) nを奇数とする。選んだ順列が長さn+12以上のサイクルを
含む確率pはp>log⁡2をみたすことを示せ。

難易度7/ 10計算量6/ 10目安30分

場合の数、確率、数列 数え上げ、余事象、定積分評価、不等式評価

方針

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

解答

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

(2)
4つの数すべてを含むサイクルは、先頭を1に固定して(1 2 3 4),(1 2 4 3),(1 3 2 4),(1 3 4 2),(1 4 2 3),(1 4 3 2)の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 では1x≦1jであり、区間全体で等号が成り立つわけではない。したがって∫jj+1dxx<1j.これを j=k,k+1,…,n について加えるとlog⁡(n+1)−log⁡k=∫kn+1dxx<∑j=kn1j.よって∑j=kn1j>log⁡(n+1)−log⁡kが示された。

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

n は奇数でj≧n+12だから、この範囲の長さのサイクルが2つ同時に存在することはない。また異なる長さの事象どうしも排反である。よってp=∑j=(n+1)/2n1j.(3)でk=n+12とすればp>log⁡(n+1)−log⁡n+12=log⁡2.したがってp>log⁡2が示された。

別解

解法2

方針

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

解答

(1)
各 i=1,2,3 に対して、ai=i となる事象を Ai とする。包除原理により、固定点を少なくとも1つもつ順列の個数は3⋅2!−3C2⋅1!+1=6−3+1=4.したがって確率は43!=23.(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−log⁡(1+u)とおくとh′(u)=1−11+u=u1+u>0,h(0)=0.よってlog⁡(1+u)<uである。ここでu=1jとするとlog⁡j+1j<1j.j=k,k+1,…,n について加えればlog⁡(n+1)−log⁡k=∑j=knlog⁡j+1j<∑j=kn1j.これで示された。

(4)
j≧(n+1)/2 を固定する。長さ j のサイクルを1つ指定した順列の個数はnCj(j−1)!(n−j)!=n!j.この範囲では2つの長いサイクルが共存しないので、各順列はどの j に対しても重複して数えられない。したがってp=1n!∑j=(n+1)/2nn!j=∑j=(n+1)/2n1j.(3)を適用するとp>log⁡(n+1)−log⁡n+12=log⁡2.

総評

難度7、目安時間30分。(1)(2)はサイクル表記と一列表示の対応確認、(3)は不等号が厳密になる理由、(4)は長さが n/2 を超えるサイクルが同時に2つ存在しないことが採点上の要点である。特に nCj(j−1)!(n−j)!=n!/j は、選択・円順列・残りの順列の3段階を言葉でも説明すると読みやすい。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る名大の場合の数の問題で問題集を作る

出典: 名古屋大学 2019年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。