COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

確率の漸化式

確率の漸化式

 確率の問題は, しばしば数列の漸化式の問題に帰着される.

問題≪完全順列の確率≫

 $n$ 人のクラスで席替えをするとき, 全員が前と同じ席にならない場合の数を $a_n,$ 確率を $p_n$ とおく.
(1)
$a_{n+2} = (n+1)(a_{n+1}+a_n)$ が成り立つことを説明せよ.
(2)
$n > 2$ のとき, $p_n-p_{n-1} = -\dfrac{1}{n}(p_{n-1}-p_{n-2})$ が成り立つことを示せ.
(3)
数列 $\{ p_n\}$ の一般項を求めよ. 必要ならば, 和の記号 $\Sigma$ を用いても良い.

解答例

(1)
$n+2$ 人のクラスの席替えを考える. 特定の人物 A, 残った $n+1$ 人の順に行っても求める場合の数は同じである. A が移動する方法は $n+1$ 通り. A の移動先にいる人物を B として, いったん A と B の席を入れ替える.
(i)
最後に A と B が入れ替わらない場合. 全員が前と同じ席にならない方法は, A 以外の $n+1$ 人が同じ席にならないように移動する方法に他ならず, $a_{n+1}$ 通りある.
(ii)
最後に A と B が入れ替わる場合. 全員が前と同じ席にならない方法は, 残りの $n$ 人が同じ席にならないように移動する方法に他ならず, $a_n$ 通りある.
(i), (ii) は排反なので, \[ a_{n+2} = (n+1)(a_{n+1}+a_n)\] が成り立つ.
(2)
$n$ 人が席替えをする方法は $n!$ 通りあるから, $p_n = \dfrac{a_n}{n!}$ である. (1) の結果から, $n > 2$ のとき, \begin{align*} p_n &= \frac{(n-1)(a_{n-1}+a_{n-2})}{n!} \\ &= \frac{n-1}{n}\cdot\frac{a_{n-1}}{(n-1)!}+\frac{1}{n}\cdot\frac{a_{n-2}}{(n-2)!} \\ &= \left( 1-\frac{1}{n}\right) p_{n-1}+\frac{1}{n}p_{n-2} \end{align*} となるので, \[ p_n-p_{n-1} = -\frac{1}{n}(p_{n-1}-p_{n-2}) \quad \cdots (R_n)\] が成り立つ.
(3)
$(R_n)$ から, $3 \leqq k \leqq n$ なる各整数 $k$ に対して, \[ p_k-p_{k-1} = -\frac{1}{k}(p_{k-1}-p_{k-2}) \quad \cdots (R_k)\] が成り立つ. $p_2-p_1 = \dfrac{1}{2!}-\dfrac{0}{1!} = \dfrac{1}{2} \neq 0$ であるので, 数学的帰納法により, \[ p_n-p_{n-1} \neq 0\] が従う. $(R_k)$ $(3 \leqq k \leqq n)$の辺々を掛け合わせて $p_k-p_{k-1}$ $(3 \leqq k \leqq n-1)$で割ると, \[ p_n-p_{n-1} = (-1)^{n-2}\frac{p_2-p_1}{n(n-1)\cdots 3} = \frac{(-1)^n}{n!}\] となる. これは $n > 1$ に対して成り立つ. ゆえに, \[ p_1 = 0, \quad p_n = \sum\limits_{k = 2}^n\frac{(-1)^k}{k!} \quad (n > 1)\] が成り立つ.

背景

  • それぞれをもとの位置と異なる位置に並び替える順列を「完全順列」または「攪乱順列」(derangement)という. $n$ 個のものの「完全順列」の総数は「モンモール数」(Montmort number)と呼ばれ, その数を求める問題は「モンモールの問題」と呼ばれる. この素朴な問題は, 本問のように身近で重要な問題である.
  • $0! = 1$ と定めると $p_n = \displaystyle\sum_{k = 0}^n\frac{(-1)^k}{k!}\ (n \geqq 0)$ と表されるので, 指数関数の「マクローリン展開」$e^x = \displaystyle\sum_{n = 0}^\infty\frac{x^n}{n!}$ から, $\displaystyle\lim_{n \to \infty}p_n = \sum_{n = 0}^\infty\frac{(-1)^n}{n!} = e^{-1}$ である.