0458-1989 东大工 数学 WEB

概率统计 排列组合 错排问题

$n$個の自然数($n\ge 1$)が小さい順に並べられているとし、これらの一部あるいは全部を並べかえることを置換操作ということにする。ただし、全く並べかえない操作も1回の置換操作と考える。置換操作のうち、すべての数字の位置を変えるような操作を完全置換操作というとき、$n$個の自然数に対して存在する完全置換操作の個数を$w_n$として、以下の問に答えよ。

(1) $w_1,w_2,w_3$ を求めよ。

(2) $w_n$ を $w_{n-1}$ と $w_{n-2}$ を用いて表せ。ただし、$n\ge 3$ とする。（結果だけでなく考え方の筋道も示すこと）

(3) $n$個の自然数に関する置換操作がすべて等確率で行われるとするとき、完全置換操作が行われる確率$P_n(n\ge 1)$を求めよ。

(4) $\underset{n\to \infty }{\lim }{P}_n$ を自然対数の底$e$を用いて表せ。

---

解答：

(1)

$$\boxed{w_1=0,w_2=1,w_3=2}$$

(2)
1を$k$番目 ($2\le k\le n$) に配置する。この$k$の選び方は$n-1$通りある。
選んだ$k$について、元の$k$の配置は以下の2つの場合に分けられる。
(i) $k$が1番目に配置される場合：残りの$n-2$個の数字による完全置換となるため、$w_{n-2}$ 通り。
(ii) $k$が1番目に配置されない場合：1番目の位置を「$k$が本来入るべき位置」と見なせば、残り$n-1$個の数字による完全置換と等価になるため、$w_{n-1}$ 通り。
以上より、

$$\boxed{w_n=(n-1)(w_{n-1}+w_{n-2})}$$

(3)
置換の総数は$n!$であるから、$P_n=\frac{w_n}{n!}$ となる。(2)の漸化式を変形すると、

$$\begin{array}{rl}{w}_n-n{w}_{n-1}& =-(w_{n-1}-(n-1)w_{n-2})\\ & =(-1{)}^{n-2}(w_2-2w_1)\\ & =(-1{)}^n(\because w_2=1,w_1=0)\end{array}$$

両辺を$n!$で割ると、

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

すなわち $P_n-P_{n-1}=\frac{(-1{)}^n}{n!}$ を得る。
$P_1=0$ より、$n\ge 2$ において

$$\begin{array}{rl}{P}_n& =P_1+\sum _{k=2}^n(P_k-P_{k-1})\\ & =0+\sum _{k=2}^n\frac{(-1{)}^k}{k!}\\ & =\sum _{k=0}^n\frac{(-1{)}^k}{k!}\end{array}$$

$n=1$のときも上式は$1-1=0$となり成立する。したがって、

$$\boxed{P_n=\sum _{k=0}^n\frac{(-1{)}^k}{k!}}$$

(4)
指数関数 $e^x$ のマクローリン展開 $e^x=\sum _{k=0}^{\infty }\frac{x^k}{k!}$ において、$x=-1$ を代入すると、

$$\begin{array}{rl}\underset{n\to \infty }{\lim }{P}_n& =\sum _{k=0}^{\infty }\frac{(-1{)}^k}{k!}\\ & =e^{-1}\end{array}$$ $$\boxed{\underset{n\to \infty }{\lim }{P}_n=\frac{1}{e}}$$

---

本题考察的是经典的错排问题，属于概率统计与离散数学中排列组合的常见模型。第一问和第二问引导我们通过递推的方式理解错排数的构成。在构造递推关系时，我们考虑将第一个元素放在第k个位置，此时根据第k个元素是否放在第一个位置，可以将剩下的情况分为规模为n-2和n-1的两个子错排问题。第三问利用第二问得到的递推公式，通过构造辅助数列求差分，可以顺利求解出错排概率的一般表达式，这里运用了累加求和的技巧。最后一问结合了微积分中的泰勒展开知识，利用自然指数函数在x等于-1处的麦克劳林展开式，求得当元素个数趋于无穷大时，发生完全错排的极限概率为e分之一。这道题将组合递推与极限级数紧密联系在了一起，过程十分经典。