[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→
乱列またはモンモールの問題
Copyright (C) virtual_high_school, 2018
§1.乱列とは
乱列とかモンモールの問題と呼ばれるものがある。ある教科書は、これを樹形図で解かせようとして、「場合の数」の単元の頭の方に持ってきている。ここでは、樹形図を使わずに解こう。それの方が分かりやすい。
【問題1】
クリスマスに$5$人の人間がそれぞれプレゼントを持ち寄って交換する。自分のプレゼントが自分にあたらないようにした場合、何通りの方法があるか。---
プレゼントを贈る側の人の集合 $\{1,2,\cdots,n \}$ からプレゼントを受け取る側の人の集合 $\{1,2,\cdots,n \}$
への1対1の写像 $\varphi$ を考える。$\varphi(i)=j$ は $i$さんが$j$さんにプレゼントを贈ることを意味する。$\varphi(i)=i$となる自然数$i$のことを不動点と呼ぶ。不動点が一つも存在しない写像が「乱列」である。この乱列が$R(n)$個あるとして、この$R(n)$を求めるのが問題である。
漸化式を作ろう。$R(n+1)$はいくつだろう。乱列であるがゆえに、$n+1$は$n+1$以外のところに移る。それ($1$から$n$までの$n$通りの可能性がある)を仮に$n$としてみる。すなわち$\varphi(n+1)=n$とする。
このとき、$n+1$に移るもの$\varphi^{-1}(n+1)$は何だろう。$n+1$でないことは確かだが、$\varphi^{-1}(n+1)=n$の場合とそれ以外の場合の2つに分けて考える。
$\varphi(n+1)$の取る値は実際には$n$通りの可能性があるので、
$ R(n+1) = n \times ( R(n-1) + R(n) ) $
これが欲しかった漸化式だ。
初期値は$R(1)=0,R(2)=1$だから、
$ R(3)=2 \times (R(1) +R(2))= 2 \times (0 +1)= 2, $
$ R(4)=3 \times (R(2) +R(3)) = 3 \times (1 +2) = 9, $
$ R(5)=4 \times (R(3)+R(4)) = 4 \times (2 +9) = 44$
で、【問題1】の答は44通りである。■
§2.乱列の確率
【問題2】
クリスマスに$5$人の人間がそれぞれプレゼントを持ち寄る。これらをランダムにシャッフルして、プレゼントを一人ひとりにあげる。誰も自分のプレゼントが自分にあたらない確率はいくらか。---
$5$個のプレゼントをともかくシャッフルして$5$人にあげる方法は全体で $5!$通りある。したがって求めるべき確率は
$\frac{R(5)}{5!} = \frac{44}{120} =\frac{11}{ 30}$■
【問題3】
$n$人のクリスマス・プレゼントにおいて乱列が起こる確率が、$n \rightarrow \infty$のときに収束する値を求めよ。---
ある一人のプレゼントが自分以外の人に渡る確率は $1-\frac{1}{n}$であり、$n$人の誰もが自分以外に渡る確率を積の法則で求め、極限をとれば、
$\displaystyle \lim_{n \rightarrow \infty} (1-\frac{1}{n})^{n} = e^{-1} =\frac{1}{e}$■
ここで、
$\displaystyle \lim_{n \rightarrow \infty} (1+\frac{x}{n})^{n} = e^{x}$
の公式を使った。
【問題4】
$n$人のクリスマス・プレゼントにおいて乱列が起こる確率の一般項を求めよ。---
$e^{x}$をテイラー展開すると、
$e^{x} = 1 +\frac{1}{1!} x +\frac{1}{2!} x^{2} +\frac{1}{3!} x^{3} +
\cdots +\frac{1}{n!} x^{n} + \cdots$
なので
$e^{-1} = 1 -\frac{1}{1!} x +\frac{1}{2!} -\frac{1}{3!} + \cdots +(-1)^{n}
\frac{1}{n!} + \cdots$
である。そうすると、求めるべき確率は
$\frac{R(n)}{n!} = 1 -\frac{1}{1!} x +\frac{1}{2!} -\frac{1}{3!} +
\cdots +(-1)^{n} \frac{1}{n!} $
ではないかと予測が立つ。実際そうなることを証明しよう。
(1) $n=1$ のとき
左辺$=\frac{R(1)}{1!} =0$
右辺$= 1 -\frac{1}{1!} =1-1=0$
で正しい。
(2) $n=2$ のとき
左辺$=\frac{R(2)}{2!} =\frac{1}{2}$
右辺$= 1 -\frac{1}{1!}+\frac{1}{2!} =1-1+\frac{1}{2}=\frac{1}{2}$
で正しい。
(3) $n$まで正しいと仮定すると、
$\frac{R(n+1)}{(n+1)!} = \frac{n \times ( R(n-1) + R(n) )}{(n+1)!}$
$=\frac{1}{n+1} \cdot \frac{R(n-1)}{(n-1)!} +\frac{n}{n+1} \cdot \frac{R(n)}{n!}$
$=\frac{1}{n+1} \{ 1 -\frac{1}{1!} + \cdots +(-1)^{n-1} \frac{1}{(n-1)!}
\} +\frac{n}{n+1} \{ 1 -\frac{1}{1!} x + \cdots +(-1)^{n} \frac{1}{n!}
\}$
$=1 -\frac{1}{1!} + \cdots +(-1)^{n-1} \frac{1}{(n-1)!} +(1-\frac{1}{n+1})(-1)^{n}
\frac{1}{n!} $
$=1 -\frac{1}{1!} + \cdots +(-1)^{n-1} \frac{1}{(n-1)!} +(-1)^{n} \frac{1}{n!}
+ (-1)^{n+1} \frac{1}{(n+1)!} $
となり、$n+1$のときにも正しくなることが示せた。■
上では一般項を「予測」して、それを証明に付したが、直接的に証明したいのであれば次のようにすればよい。
$\frac{R(n+1)}{(n+1)!} = \frac{1}{n+1} \cdot \frac{R(n-1)}{(n-1)!} +(1-\frac{1}{n+1})
\cdot \frac{R(n)}{n!}$
より
$\frac{R(n+1)}{(n+1)!} -\frac{R(n)}{n!}=- \frac{1}{n+1} \{ \frac{R(n)}{n!}
-\frac{R(n-1)}{(n-1)!} \}$
よって
$\frac{R(n)}{n!} -\frac{R(n-1)}{(n-1)!} = (-\frac{1}{n})(-\frac{1}{n-1})
\cdots (-\frac{1}{3})\{ \frac{R(2)}{2!} -\frac{R(1)}{1!} \}=(-1)^{n} \frac{1}{n!}
$
これで階差数列が分かったので、元の数列の一般項が分かって
$\frac{R(n)}{n!} = \frac{R(1)}{1!} + \displaystyle \sum_{k=2}^{n} (-1)^{k} \frac{1}{k!}$
$=1-\frac{1}{1!}+\frac{1}{2!} -\frac{1}{3!} + \cdots + (-1)^{n} \frac{1}{n!}$
■
§3.乱列の一般項
最後に乱列の一般項を求めておこう。
【問題5】
$n$個の乱列は何個あるか。その一般項を求めよ。---
分母を払って
$R(n) =n! \{ 1 -\frac{1}{1!} x +\frac{1}{2!} -\frac{1}{3!} + \cdots +(-1)^{n} \frac{1}{n!} \}$■
[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→