2016/8/14 
場合の数
$0,1,2,9,44,265,1854,14833,133496,\cdots$
$1,2,..,n$ の数が書かれた $n$ 枚のカードを一列に並べるとき，$k$ 番目 ($1 \le k \le n$) が $k$ でない並べ方を完全順列という．
完全順列のことを，攪乱順列 (かくらんじゅんれつ) ともいいます．また，完全順列の総数 $a_n$ をモンモール数と言ったりもします．小さい $n$ に対して，モンモール数 $a_n$ を求めてみましょう．以下では，左から数えて $k$ 番目が $k$ でない並べ方を考えます．(右から数えた場合でも結果は変わりません)
$n=1$ のとき： 一番目が必ず $1$ のカードになってしまうので，$a_1=0$ です．
$n=2$ のとき： 全部で $2!=2$ 通りの並べ方がありますが，完全順列となるのは $2 1$ と並んでいるときのみなので，$a_2=1$ です．
$n=3$ のとき： 全部で $3!=6$ 通りの並べ方がありますが，完全順列となるのは $2 3 1$ ， $3 1 2$ の $2$ 種類のみなので，$a_3=2$ です．
$n=4$ のとき： 全部で $4!=24$ 通りの並べ方がありますが，完全順列となるのは以下の表から，$9$ 種類あるので，$a_4=9$ です．
\begin{array}{cccc} \large{①}&\large{②}&\large{③}&\large{④} \\ 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&1&2 \\ 4&3&2&1 \\ \end{array}
$n$ がもっと大きい数の場合には，上のように単純に数えるのは大変です．どのようにして一般の $n$ に対してモンモール数を求めればよいのでしょうか．幸いなことに上手い方法が知られています．
$a_n$ をモンモール数とします (すなわち完全順列の総数). 数列 $a_n$ について，漸化式を立ててみましょう．自然数 $k$ ($2 \le k \le n$) をひとつ固定します.いま，$1$ という数が書かれたカードが $k$ 番目にあるとします (あとで，$k$ を $2$ から $n$ まで動かせば，完全順列の総数が得られる) .このとき，完全順列は次の $2$ つの場合に分けることができます．
case1： $k$ という数が書かれたカードが $1$ 番目にある．
case2： $k$ という数が書かれたカードが $1$ 番目にない． $2$ つのケースは当然，同時に起こることはありません．この $2$ つのケースそれぞれについて，$k$ を動かします．
case1のとき $k$ の選び方は $n-1$ 通りあります．また，$1$ と $k$ を除く $n-2$ 通りのカードの並べ方は $a_{n-2}$ 通りなので，結局case1の並べ方は $(n-1)a_{n-2}$ 通り．
case2のとき $k$ の選び方は $n-1$ 通りあります．また，$k$ を除く $n-1$ 通りのカードの並べ方は $a_{n-1}$ 通りなので，結局case2の並べ方は $(n-1)a_{n-1}$ 通り．($k$ は $1$ 番目においてはいけないことに注意)
以上より， 次の漸化式が得られます．上の節で確かめたモンモール数の値が成り立っていることを確認してみてください．
$a_n$ をモンモール数とするとき，次の漸化式が成り立つ． $$\large a_n=(n-1)(a_{n-1}+a_{n-2}) (n \ge 3)$$
完全順列の漸化式から，一般項を求めることができます．特性方程式の考え方を用いて，漸化式 $a_n=(n-1)(a_{n-1}+a_{n-2})$ を次のように変形します． $$a_n-na_{n-1}=-(a_{n-1}-(n-1)a_{n-2})$$ これをひたすら続けていくと， $$a_n-na_{n-1}=-(a_{n-1}-(n-1)a_{n-2})=(-1)^2(a_{n-2}-(n-2)a_{n-3})=\cdots$$ $$=(-1)^{n-2}(a_2-2a_1)=(-1)^{n}$$ 最左辺と最右辺を $n!$ で割ると， $$\frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}=\frac{(-1)^n}{n!}$$ これより， $$\frac{a_n}{n!}=\frac{a_1}{1!}+\sum_{k=2}^n\frac{(-1)^k}{k!}=\sum_{k=2}^n\frac{(-1)^k}{k!}$$ となるので，一般項が求められます．
モンモール数 $a_n$ の一般項は次の式で与えられる．
$$\large a_n=n!\sum_{k=2}^n\frac{(-1)^k}{k!}$$ $$\large=n!\left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\cdots+\frac{(-1)^{n-1}}{(n-1)!}+\frac{(-1)^n}{n!}\right)$$
完全順列と確率の問題は大学入試でもしばしば題材にされることがあります．確率 (の極限) に自然対数の底 $e$ が出てくるというなんとも興味深い現象が起こる例として有名です．
$1,2,..,n$ の数が書かれた $n$ 枚のカードを一列に並べる並べ方の総数は $n!$ 通りなので，無造作にカードを一列に並べたとき，それが完全順列となっている確率は， $$\frac{a_n}{n!}=\left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\cdots+\frac{(-1)^{n-1}}{(n-1)!}+\frac{(-1)^n}{n!}\right)$$ です．右辺の $n \to \infty$ での極限は $\frac{1}{e}=0.367879…$ になることが知られています．また，右辺の収束は非常にはやく，$n=7$ のときでさえ，(右辺)=$0.36785\cdots$ となります．したがって，$n$ がある程度大きければ，無造作にカードを一列に並べたとき，それが完全順列となっている確率は，ほとんど $\frac{1}{e}$ ということが言えます．
