プレゼント交換をすると e が現れる。〜完全順列とモンモール数の一般項〜

あなたはあるパーティに参加し、参加者が $1$ 人 $1$ 個ずつ持参したプレゼントの交換をします。（但し、各々の参加者がプレゼントを選ぶ方法は同様に確からしいものとします。）

ここで、全員が他の人のプレゼントを貰えたら成功とし、誰か $1$ 人でも自分のプレゼントを受け取ってしまった場合は失敗とします。

例えば、$1$ 人では自分のプレゼントを受け取らざるを得ないので成功確率は $0$ ですね。

また、$2$ 人では $2$ 人とも自分のプレゼントを受け取り失敗するか、$2$ 人とも相方のプレゼントを受け取り成功するかの $2$ 通りなので成功確率は $\displaystyle \frac{1}{2}$ ですね。

さて、

参加者が増えれば増えるほど
プレゼント交換の成功確率は
何％に近づいてゆくでしょうか？

選択肢を挙げておきます。

約 $0$ ％
約 $7$ %
約 $17$ ％
約 $27$ ％
約 $37$ ％
約 $47$ ％
約 $100$ ％

是非、答えを予想して読み進めてみてください。

完全順列とは何か？
モンモール数の一般項を求めよう！
成功確率を計算しよう！
最後に。

完全順列とは何か？

完全順列とは、一言で言うと

左から $k$ 番目が $k$ でないような順列

のことを言います。

わかりやすいように、参加者を $5$ 人とします。参加者全員に番号 $1,2,3,4,5$ を割り振り、自分のプレゼントに自分の番号を書きます。

プレゼントの交換後、参加者に左から番号順に並んでもらうと、プレゼントに書かれた数によって順列ができますね。

上の絵のようにプレゼント交換が成功した場合の順列 $4\ 5\ 2\ 1\ 3$が「完全順列」なのです。

ここで、一般に $n$ 人の場合の完全順列の数をモンモール数と呼び

$$!n$$

と表します。（階乗 $n!$ に似ていますね…！）

例えば、冒頭で見たように、$1$ 人では自分のプレゼントを受け取らざるを得ないので $!1=0$ となります。

また、$2$ 人では $2$ 人とも自分のプレゼントを受け取り失敗するか、$2$ 人とも相方のプレゼントを受け取り成功するかのいずれかなので $!2=1$ となります。

モンモール数の一般項を求めよう！

$!3$, $!4$ を樹形図で求める。

$!1=0$ や $!2=1$ は先ほど見たので、実験として、その続きの $!3$ や $!4$ を求めてみましょう。

$!3$ について、$1$ 番目は $\fbox{1}$ 以外なので $\fbox{2}$ または $\fbox{3}$ ですね。$1$ 番目が $\fbox{2}$ のとき、$2$ 番目が $\fbox{1}$ となると $3$ 番目が $\fbox{3}$ となってしまい失敗です。よって、$2$ 番目が $\fbox{3}$ で $3$ 番目が $\fbox{1}$ となります。$1$ 番目が $\fbox{3}$ のときも同様に $\fbox{3}\,\fbox{1}\,\fbox{2}$ があります。これより、樹形図は

となるので

$$!3=2$$

と求めることができます。

$!4$ について、$1$ 番目は $\fbox{2}$ または $\fbox{3}$ または $\fbox{4}$ ですね。

$1$ 番目が $\fbox{2}$ のとき、$2$ 番目が $\fbox{1}$ となると $1$ 番目と $2$ 番目で交換が完結してしまうので、残りの $3$ 番目と $4$ 番目の $2$ 人が交換を行います。よって、この場合の成功する場合の数は $!2=1$ となります。

$1$ 番目が $\fbox{2}$ で $2$ 番目が $\fbox{1}$ ではない場合、$1$ 番目の $\fbox{2}$ を除いた $3$ 人で完全順列を考えることになります。よって、この場合の成功する場合の数は $!3=2$ となります。

これより、$1$ 番目が $\fbox{2}$ のときの樹形図は

となり、$1+2=3$ 通りがあります。$1$ 番目が $\fbox{3}$ や $\fbox{4}$ のときも同様に $3$ 通りがあるので

$$!4=3\times(1+2)=9$$

と求めることができます。（余裕のある方は $1$ 番目が $\fbox{3}$ や $\fbox{4}$ のときの樹形図も書いてみてください！）

$!5$ を工夫して求める。

$!4$ を求めたときの議論を正確に行うことによって、樹形図を書かずとも $!5$ を求めることができます。

完全順列の $1$ 番目は $\fbox{2}$ または $\fbox{3}$ または $\fbox{4}$ または $\fbox{5}$ ですね。

$1$ 番目が $\fbox{2}$ のときを考えましょう。

$2$ 番目が $\fbox{1}$ となると $1$ 番目と $2$ 番目で交換が完結するので、残りの $3$ 人が交換を行います。よって、この場合の成功する場合の数は $!3$ となります。

$2$ 番目が $\fbox{1}$ ではない場合、$1$ 番目の $\fbox{2}$ を除いた $3$ 人で完全順列を考えることになります。よって、この場合の成功する場合の数は $!4$ となります。

これより、$1$ 番目が $\fbox{2}$ のときの場合の数は $!3+!4$ 通りになります。

$1$ 番目が $\fbox{3}$ や $\fbox{4}$ や $\fbox{5}$ のときも同様に $!3+!4$ 通りがあるので

$$!5=4\times(!3+!4)$$

という関係式が成り立つのです。具体的には $!3=2$ かつ $!4=9$ であるので

$$!5=4\times(2+9)=44$$

を得るのです。

$!n$ はこう書ける。

$5$ 人の場合、$3$ 人と $4$ 人の完全順列を考えて求めたモンモール数 $!3$ と $!4$ を用いて、$!5=4\times(!3+!4)$ という関係式によってモンモール数を求めていました。

$!5$ を求めたときの $5$ を $n$ に一般化することによって、同様に
\begin{align}
!n=(n-1)\{!(n-2)+!(n-1)\}\qquad(n=3,4,\cdots)\tag{1}
\end{align}

という関係式（三項間漸化式！）が成り立ちます。但し、
\begin{align}
!1=0,\qquad !2=1\tag{2}
\end{align}

です。

さて、式 (1),(2) から $!n$ の一般項を求めましょう。

まず、漸化式 (1) の右辺の括弧を外して
$$!n=(n-1)\{!(n-2)\}+(n-1)\{!(n-1)\}$$

両辺から $n\{!(n-1)\}$ を引いて整理することで
$$!n-n\{!(n-1)\}=-[!(n-1)-(n-1)\{!(n-2)\}]$$

両辺を $(-1)^n$ で割ることで
$$\frac{!n-n\{!(n-1)\}}{(-1)^n}=\frac{!(n-1)-(n-1)\{!(n-2)\}}{(-1)^{n-1}}$$

つまり、$n=2,3,4,\cdots$ について $\displaystyle \frac{!n-n\{!(n-1)\}}{(-1)^n}$ は一定の値をとるので
$$\frac{!n-n\{!(n-1)\}}{(-1)^n}=\frac{!2-2\times !1}{(-1)^2}=1$$
すなわち
\begin{align}
!n-n\{!(n-1)\}=(-1)^n\tag{3}
\end{align}
を得ます。

それでは、式 (2),(3) から $!n$ の一般項を求めましょう。

まず、漸化式 (3) の両辺を $n!$ で割って
$$\frac{!n}{n!}-\frac{!(n-1)}{(n-1)!}=\frac{(-1)^n}{n!}$$

次に、階差数列の考え方から、$n=2,3,\cdots$ について
\begin{align}
\frac{!n}{n!}
&=\frac{!1}{1!}+\sum_{k=2}^n\frac{(-1)^k}{k!}\\
&=\sum_{k=2}^n\frac{(-1)^k}{k!}\\
&=\sum_{k=0}^n\frac{(-1)^k}{k!}
\end{align}

これは、$n=1$ のときは成り立たないので
\begin{align}
!1&=0,\\
!n&=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\quad(n=2,3,\cdots)
\end{align}
を得ます。

これが求めたかった一般項です！

成功確率を計算しよう！

全ての順列を考えると $n!$ 通りですから、成功確率 $p_n$ は

$$p_n=\frac{!n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}\quad(n=2,3,\cdots)$$

によって計算することができます。

我々は、

$n$ が大きくなるほど
確率 $p_n$ は何に近づくか？

という問に応えたかったわけです。つまり、数学的には

極限 $n\to\infty$ で数列 $\{p_n\}$ は収束するか？
収束するならば、その極限値はいくつか？

を考えれば良いですね。

極限 $n\to\infty$ を考えるので、$n=1$ の場合は無視して良いです。

確率 $\displaystyle p_n=\sum_{k=0}^n\frac{(-1)^k}{k!}$ に形が似ているものとして、指数関数のマクローリン展開

$$e^x=\sum_{n=0}^\infty \frac{x^n}{n!}$$

があります。これは $x=-1$ でも成り立つので
\begin{align}
\frac{1}{e}
&=e^{-1}\\
&=\sum_{n=0}^\infty \frac{(-1)^n}{n!}\\
&=\lim_{n\to\infty}\sum_{k=0}^n \frac{(-1)^k}{k!}\\
&=\lim_{n\to\infty}p_n
\end{align}

を得るのです！

以上より、極限 $n\to\infty$ で数列 $\{p_n\}$ は収束し、その極限値は

$$\lim_{n\to\infty}p_n=\frac{1}{e}=0.367879441\cdots$$

となります。

答えは

e. 約 $37$ %

でした！！