IV横浜市立大学 2014年 数学 第IV問解答・解説

(1) $k$ 個のボールを置いた後の並び方がすべて等確率であることを示す。$k=1$ のときは並び方が一通りだけなので成り立つ。$k-1$ 個の段階ですべての並びが確率 $1/(k-1)!$ で生じるとする。特定の $k$ 個の並びから $k$ 番のボールを除けば、直前の並びと挿入位置が一意に定まる。従ってその並びの確率は $$\displaystyle \frac{1}{(k-1)!}\cdot\frac1k=\frac1{k!}.$$ 帰納法より、$n!$ 通りは一様。$i$ 番のボールが左から $j$ 番目となる並びは残り $n-1$ 個の並べ方 $(n-1)!$ 通りだから、求める確率は $$\displaystyle \frac{(n-1)!}{n!}=\frac1n.$$

(2) 列を左から $a_1,\ldots,a_n$ とし、$p<q$ かつ $a_p>a_q$ となる組の個数を $I$ とする。隣り合う $a_p>a_{p+1}$ を交換すると、その二つの順序による $I$ の寄与は1から0になる。他のボールとの相対順序は変わらないため、交換のたびに $I$ はちょうど1減る。$I$ は負でない整数なので交換は有限回で止まる。停止後は隣り合う下降がなく、列は番号順である。

(3) (2)の交換では毎回 $I$ がちょうど1減り、番号順の列では $I=0$。従って交換回数は初期列の $I$ と等しく、交換できる箇所の選び方によらない。

(4) $r<i$ とする。初期列で $i$ が $r$ より左にある場合、最終列では順序が逆になる。相対順序が変わるのはこの2個を隣り合わせて交換したときだけであり、その後に順序が戻ることはないので、2個はちょうど一度交換される。初期列で $r$ が $i$ より左なら、初期順序は最終順序と同じなので交換されない。よって $i$ がより小さい番号のボールと交換する回数の期待値は $$\displaystyle E_i=\sum\limits _{r=1}^{i-1}\frac12=\frac{i-1}{2},$$ (1)で初期列は一様であり、各対の左右の順序は同確率だからである。全交換回数の期待値は $$\displaystyle \sum\limits _{i=1}^nE_i=\frac12\sum\limits _{i=1}^n(i-1) =\frac12\cdot\frac{n(n-1)}2=\frac{n(n-1)}4.$$