京都大学 2009年 理系 第3問（乙） 解説

方針・初手

カード全体の並び順を考えるのではなく、最初一番下にあった「ターゲットのカード」が「下から何番目にあるか（＝下に何枚のカードがあるか）」だけに着目して状態推移を考えます。1回の試行でこの枚数がどのように変化するかの確率を求め、$n$ 回の試行で目標の状態に到達するためのルートを場合分けして計算します。

解法1

最初一番下にあったカード（番号 $n$）を「ターゲット」と呼ぶ。ターゲットの下にあるカードの枚数を $k$ とし、これを現在の状態とする。初期状態は $k=0$ であり、ターゲットが山の一番上にきている状態は $k=n-1$ である。

1回の試行において、状態 $k$ がどのように遷移するかを考える。ターゲットが一番上にない（$0 \leqq k \leqq n-2$）とき、取り出される一番上のカードはターゲットではない。これを $n$ 箇所のいずれかに戻すとき、ターゲットの下（$k+1$ 箇所）に入れれば状態は $k+1$ になり、ターゲットより上（$n-k-1$ 箇所）に入れれば状態は $k$ のままである。

• $k \to k+1$ になる確率：$\dfrac{k+1}{n}$
• $k \to k$ のままとなる確率：$\dfrac{n-k-1}{n}$

ターゲットが一番上にある（$k=n-1$）とき、取り出されるのはターゲット自身である。

• $n-1 \to n-1$ のまま（一番上に戻す）となる確率：$\dfrac{1}{n}$
• 状態が減少する（それ以外の場所に入れる）確率：$\dfrac{n-1}{n}$

目標は、$n$ 回の試行を終えて $k=n-1$ となる確率である。1回の試行で $k$ は最大 $1$ しか増加しないため、$n$ 回の試行で $k=0$ から $k=n-1$ に到達するには、$k$ が増加する（$+1$）遷移がちょうど $n-1$ 回必要である。残りの1回は、$k$ が変化しない（$+0$）遷移でなければならない（減少が1度でも起きると到達不可能になるため）。

停滞（$+0$）する試行が $n$ 回のうち何回目かで場合分けをする。

(i) $j$ 回目（$1 \leqq j \leqq n-1$）の試行で停滞し、他の $n-1$ 回はすべて増加する場合

停滞する直前の状態は $k=j-1$ である。$j$ 回目の試行で状態が維持される確率は $\frac{n-j}{n}$ である。他の $n-1$ 回の試行では状態が $+1$ ずつ増加するため、その遷移確率の積は

$$ \frac{1}{n} \times \frac{2}{n} \times \cdots \times \frac{n-1}{n} = \frac{(n-1)!}{n^{n-1}} $$

したがって、このパターンの確率は

$$ \frac{n-j}{n} \cdot \frac{(n-1)!}{n^{n-1}} = \frac{(n-j)(n-1)!}{n^n} $$

(ii) $n$ 回目の試行で停滞し、最初の $n-1$ 回はすべて増加する場合

$n-1$ 回目までの試行で状態は $k=n-1$ に達している。その確率は

$$ \frac{1}{n} \times \frac{2}{n} \times \cdots \times \frac{n-1}{n} = \frac{(n-1)!}{n^{n-1}} $$

$n$ 回目の試行は状態 $n-1$ からの遷移である。ターゲットが一番上にある状態から、再び一番上に戻る確率であるため $\frac{1}{n}$ である。したがって、このパターンの確率は

$$ \frac{(n-1)!}{n^{n-1}} \cdot \frac{1}{n} = \frac{(n-1)!}{n^n} $$

(i), (ii) は互いに排反であるから、求める確率 $P$ はこれらの和となる。

$$ P = \frac{(n-1)!}{n^n} + \sum_{j=1}^{n-1} \frac{(n-j)(n-1)!}{n^n} = \frac{(n-1)!}{n^n} \left( 1 + \sum_{j=1}^{n-1} (n-j) \right) $$

ここで、$\sum_{j=1}^{n-1} (n-j) = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$ であるから、

$$ P = \frac{(n-1)!}{n^n} \left( 1 + \frac{n(n-1)}{2} \right) = \frac{(n-1)! (n^2 - n + 2)}{2n^n} $$

解説

一見するとカード全体の順列を考えなければならないように思えますが、特定の1枚のカード（ターゲット）の「位置（下からの枚数）」だけに注目することで、状態遷移を劇的に簡略化できるのが最大のポイントです。「1回あたり最大でも1つしか上に進めない」という制約から、$n$ 回で $n-1$ 段進むための経路が限られることに気づけば、あとは反復試行の要領で和を計算するだけです。一番上に到達した後の遷移確率が異なる点（場合分けの ii）に注意が必要です。

答え

$$ \frac{(n-1)! (n^2 - n + 2)}{2n^n} $$