https://spherical-harmonics.hateblo.jp/entry/Waseda/2025/Rikou

2025.02.17記

[3] $1$ から $n$ までの異なる自然数が $1$ つずつ書かれた $n$ 枚のカードが一列に並んでいる．このとき，どのカードも現在とは異なる位置に移動するように並べ替えてできる順列の総数を $a_n$ と表し，並べ替えの総数 $n!$ に占める $a_n$ の割合を $p_n$ で表す．例えば，
$a_1=0$ ， $p_1=0$ ， $a_2=1$ ， $p_2=\dfrac{1}{2}$ ， $a_3=2$ ， $p_3=\dfrac{1}{3}$
である．次の問いに答えよ．

(1) $a_4$ の値を求めよ．

(2) $n\geqq 3$ のとき， $a_n$ を $a_{n-1}$ と $a_{n-2}$ を用いて表せ．

(3) $n\geqq 2$ のとき， $p_n-p_{n-1}$ を $n$ を用いて表せ．

2025.02.17記

本問のテーマ

モンモールの問題（攪乱順列，完全順列）

[解答]
$n\geqq 3$ とする．

「 $n$ 」番目のカードが「 $i$ 」のとき

(a) 「 $i$ 」番目のカードが「 $n$ 」なのは，残り $n-2$ 枚のカードの並べかえで $a_{n-2}$ 通り

(b) 「 $i$ 」番目のカードが「 $n$ 」以外の場合，「 $n$ 」番目のカードを隠してカード「 $n$ 」をカード「 $i$ 」だと思うと， $n-1$ 枚のカードの並べかえで $a_{n-1}$ 通り

となる． $i$ の選び方は $n-1$ 通りあるので
$a_n=(n-1)(a_{n-1}+a_{n-2})$
が成立する．

(1) $a_4=3(a_2+a_1)=9$

(2) $a_n=(n-1)(a_{n-1}+a_{n-2})$

(3) (2) より $p_n=\dfrac{n-1}{n}p_{n-1}+\dfrac{1}{n}p_{n-2}$ であるから
$p_n-p_{n-1}=\dfrac{-1}{n}(p_{n-1}-p_{n-2})$ $=\dfrac{(-1)^{n-2}}{n\cdot (n-1)\times \cdots \times 3}(p_{2}-p_{1})$ $=\dfrac{(-1)^{n}}{n!}$
となる．

これから $p_n\to\dfrac{1}{e}$ （ $n\to\infty$ ）となる．この交代級数 $\{p_n\}$ の収束は早いので $n=10$ 程度で $p_n≒\dfrac{1}{e}$ は実用的な近似となっている．