【数学小話】完全順列、プレゼント交換会の総数と確率

こんなところにも自然対数eが登場するという、不思議な例を見てみます。

問題
漸化式を作る
一般項を求める
プレゼント交換がうまくいく確率
1/eに収束する理由

問題

n個の整数 1,2,3,...,nを、１番目に１が、２番目に２が、...、n番目にnが来ないように、1列に並べるのは何通りか。

これは、

n人がプレゼントを持ち寄って、ランダムに配ったとき、全員が自分のでないプレゼントを受け取るような配り方は何通りあるか。

と同じ問題です。

完全順列

n個の整数 1,2,3,...,nを、i番目（1≦i≦n）にiが来ないように1列に並べる順列、これを完全順列といい、完全順列の総数をモンモール数といいます。プレゼント交換会の配り方の総数とも言えます。

・n=1 のとき
1番目に1が来ないように並べるのは不可能なので、0通り。

・n=2 のとき
1,2 を、1文字目に1が来ないように、2文字目に2が来ないように並べるのは、
(2,1)
と並べたときのみ。1通り。

・n=3 のとき
1文字目に1が、2文字目に2が、3文字目に3が来ないように並べるのは、
(2,3,1), (3,1,2)
の2通り。

・n=4 のとき
(2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,2,1), (4,3,1,2)
の9通り。

モンモール数を小さい順に書くと、
0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, …
となります。増加スピードがなかなか速いのが分かります。

漸化式を作る

n番目のモンモール数を $a_n$ とします。つまり、
$a_1=0,\ a_2=1,\ a_3=2,\ a_4=9,\ a_5=44,\ a_6=265,...$
となっています。 $a_nとa_{n-1}とa_{n-2}$ の間に成り立つ関係を考えます。

n個の完全順列を作ろうとします。まず数字nをi番目に置くとします。(当然、i≠nです)ここで、数字iをどこに置くかで場合分けをします。

f:id:hby:20191020110256j:plain

(i) 数字iをn番目に置くとき

残った
1, 2, 3, ..., i-1, i+1, i+2, ..., n-1
というn-2個の数字は、どんな制限で置いていくかというと、

1は1番目以外、2は2番目以外、...、i-1はi-1番目以外、i+1はi+1番目以外、...、n-1はn-1番目以外に置かなければなりません。このn-2個の数字を配置する総数はまさに $a_{n-2}$ に等しいです。

(ii) 数字iをn以外に置くとき

今のところ、1~nのうちn以外のn-1個の数字が配置待ちです。これらはどんな制限で置かれていくかというと、

1は1番目以外、2は2番目以外、...、i-1はi-1番目以外、i+1はi+1番目以外、...、n-1はn-1番目以外、そして、iはn番目以外

という制限になります。ここで、最後の「iはn番目以外」は、数字iが数字nだと思えば、配置の総数はまさに $a_{n-1}$ に等しいです。
(ちょっとここだけ考え方が難しいかも)

ということで、数字nをi番目に配置するとき、順列が $a_{n-1}+a_{n-2}$ 個あります。数字nは1番目からn-1番目に配置できるので、

$\LARGE{a_{n}=(n-1)(a_{n-1}+a_{n-2})}$

ついに関係式が得られました。よってモンモール数は、

$\large{a_1=0,\ a_2=1,\ a_{n}=(n-1)(a_{n-1}+a_{n-2})\ (n\geqq3)}$

で表される数列です。試しにn=3,4を代入してみると、

$a_{3}=2(a_{2}+a_{1})=2\\a_{4}=3(a_{3}+a_{2})=9$

となり、実際の値と一致しています。

一般項を求める

step1.うまく漸化式を変形していきます。まず、
$a_{n}=(n-1)(a_{n-1}+a_{n-2})$
を、うまーく変形して、

$a_{n}-na_{n-1}=-(a_{n-1}-(n-1)a_{n-2})...①$

とします。この式のnをn-1,n-2,...に置き換えた式は、

$a_{n-1}-(n-1)a_{n-2}=-(a_{n-2}-(n-2)a_{n-3})...②\\a_{n-2}-(n-2)a_{n-3}=-(a_{n-3}-(n-3)a_{n-4})...③$

となります。nを置き換える値を1ずつ減らしていって、3に置き換えた式は、

$a_{3}-3a_{2}=-(a_{2}-2a_{1})=-1...④$

となります。これより、①の右辺に②を代入し、さらに③を代入し、...というのを繰り返して④までやると、

$a_{n}-na_{n-1}\\=-(a_{n-1}-(n-1)a_{n-2})\\=(-1)^2(a_{n-2}-(n-2)a_{n-3})\\...\\=(-1)^{n-2}(a_{2}-2a_{1})=(-1)^{n-2}$

となります。 $(-1)^{n-2}=(-1)^{n}$ だから、

$\large{a_{n}-na_{n-1}=(-1)^{n}...⑤}$

となります。

step2. ⑤の式を両辺 $n!$ で割って、

$\displaystyle\frac{a_{n}}{n!}-\frac{a_{n-1}}{(n-1)!}=\frac{(-1)^{n}}{n!}$

ここで、 $\displaystyle b_n=\frac{a_n}{n!}$ とすれば、

$\displaystyle b_n-b_{n-1}=\frac{(-1)^{n}}{n!}$

より、数列 $\{b_n\}$ の階差数列が分かりました。また、 $b_1=a_1=0$ だから、

$\displaystyle b_n=b_1+\sum_{k=1}^{n-1}\frac{(-1)^{k+1}}{(k+1)!}\\\displaystyle \large{b_n=\sum_{k=2}^{n}\frac{(-1)^{k}}{k!}=\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+...+\frac{(-1)^n}{n!}}$

最後に、 $b_n$ を $a_n$ に戻して、

$\displaystyle \large{a_n=n!\sum_{k=2}^{n}\frac{(-1)^{k}}{k!}\\\displaystyle\underline{a_n=n!\Biggr\{\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+...+\frac{(-1)^n}{n!}\Biggr\}}}$

プレゼント交換がうまくいく確率

n人で持ち寄ったプレゼントを、ランダムに配ったとき、どの人も自分のでないプレゼントを受け取るように配れる確率は、

$\displaystyle\frac{a_n}{n!}=b_n=\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+...+\frac{(-1)^n}{n!}$

です。実は、nを正の無限大に飛ばすと、

$\displaystyle\lim_{n\to\infty}\frac{a_n}{n!}=\frac{1}{e}$

となります。こんなところにネイピア数eが登場するとは。
ということで、集まる人数が多ければ多いほど、うまくいく確率は1/e≒37%に近づきます。

1/eに収束する理由

完全に高校の範囲外です。指数関数 $e^x$ のマクローリン展開が、

$\displaystyle e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}...$

であり、ここにx=-1を代入すれば、最初の2項が打ち消しあって、

$\displaystyle e^{-1}=\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-...$

となります。以上。

written by k

日比谷高校のススメ

日比谷高校出身者たちが日比谷高校の紹介や、勉強に関する様々なことを語ります。

【数学小話】完全順列、プレゼント交換会の総数と確率

問題

漸化式を作る

一般項を求める

プレゼント交換がうまくいく確率

1/eに収束する理由