乱列またはモンモールの問題

§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^{-1}(n+1)=n$のときは、
　　　$ \varphi : n \rightarrow n+1, $
　　　$ \varphi : n+1 \rightarrow n $
だから、$n$と$n+1$の間は互換になっているだけなので、あとは$1 \leq i \leq n-1$の上での乱列の個数を数えればよい。それは$R(n-1)$である。
　　　
$\varphi^{-1}(n+1) = r <n$のときは、
　　　$ \varphi : r \rightarrow n+1, $
　　　$ \varphi : n+1 \rightarrow n $
となるが、ここでちょっと手術をする。行き先の$n$と$n+1$を交換して
　　　$ \varphi : r \rightarrow n, $
　　　$ \varphi : n+1 \rightarrow n+1 $
とする。$n+1$が不動点になってしまうが、その他の自然数は不動点ではない。だから、この場合の乱列の個数は$R(n)$である。

$\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に戻る　このページを閉じる