5大阪大学 2013年 数学 第5問解答・解説

(1) 球 $K_i$ が入った箱を $H_{f(i)}$ とおく。全ての箱に球が1個ずつ入るので、$f$ は $\{1,2,\ldots,n\}$ の置換である。$i\geq 2$ で $f(i)\neq i$ なら、$K_i$ が来たときには $H_i$ は既に埋まっていた。その箱に入れた球はある $K_j$（$j<i$）だから、置換 $f$ の巡回において $i$ の直前にある番号は $i$ より小さい。

この条件から、$1$ を含まない非自明な巡回は存在しない。実際、その巡回の最小番号を $m$ とすると、$m$ の直前の番号は $m$ より大きくなり、上の条件に反する。したがって非自明な巡回は高々1つであり、$1$ を含むなら、その形は $$(1,s_1,s_2,\ldots,s_r),\qquad 1<s_1<s_2<\cdots<s_r$$ である。よって $n$ がこの巡回に含まれなければ $f(n)=n$ であり、含まれれば $n$ は巡回中の最大番号なので $f(n)=1$ となる。いずれの場合も、$K_n$ が入る箱は $H_n$ または $H_1$ である。

(2) 上の巡回に含まれる $2$ 以上の番号の集合を $S$ とする。$S$ は $\{2,\ldots,n\}$ の任意の部分集合であり、各 $S$ に対して対応する巡回は一意である。$S=\varnothing$ のとき $K_1$ は $H_1$ に入り、そうでないとき $K_1$ は $S$ の最小番号の箱に入るので、その確率はいずれも $1/n$ である。また、$i\in S$ では $K_i$ は既に埋まった $H_i$ を避けて、空箱 $n-i+1$ 個の中から巡回で次に指定された箱を選ぶ。したがって $$\displaystyle P(S)=\frac1n\prod\limits _{i\in S}\frac1{n-i+1}.$$ 一方、$K_{n-1}$ が $H_{n-1}$ に入るのは、$n-1\notin S$ のときである。よって $$\displaystyle \begin{aligned} P(K_{n-1}\text{ が }H_{n-1}\text{ に入る}) &=\frac1n\prod\limits _{\substack{2\leq i\leq n\\i\neq n-1}} \left(1+\frac1{n-i+1}\right)\\ &=\frac1n\cdot \frac{\displaystyle\prod\limits _{r=1}^{n-1}\left(1+\frac1r\right)} {1+\frac12} =\frac1n\cdot\frac{n}{3/2} =\frac23. \end{aligned}$$ ここで $\displaystyle \prod\limits _{r=1}^{n-1}(1+1/r)=n$ を用いた。

球と箱の対応を置換として見る。各非自明巡回は1を含み、順序が増加するので部分集合で分類できる。その確率を積で表し、$K_{n-1}$の固定点確率を計算する。