3京都大学 2009年 数学 第3問解答・解説

カードnより上にあるカードの枚数をkとする。最初は $k=n-1$、目標は $k=0$。kが正なら、取り出した一番上のカードをカードnより上へ戻す操作はk通りでkを保ち、nの下へ戻す操作はn−k通りでkを1減らす。k=0でkを保つ操作は一番上に戻す1通りだけである。

$k=n-1$ から0へ行くためにはkを減らす操作を少なくともn−1回行う。操作は全部でn回なので、残る1回は、(i) k=0到達後にそこへ留まるか、(ii) いずれかの正のkで値を保つ。減少操作の選択数は各段階の積 $$\displaystyle \prod\limits _{k=1}^{n-1}(n-k)=(n-1)!$$ である。(i)は最後に留まる1通りを掛けて $(n-1)!$ 通り。(ii)で値を保つ段階kを指定すると、そこではk通りなので、全体は $$\displaystyle (n-1)!\sum\limits _{k=1}^{n-1}k=(n-1)!\frac{n(n-1)}2$$ 通り。従って有利な列数は $(n-1)!(n^2-n+2)/2$。各回にn個の挿入位置があるため全列は $n^n$ 通りで、確率は $$\displaystyle \frac{(n-1)!(n^2-n+2)}{2n^n}.$$