モンモール数

説明

$1, \cdots , n$ の順列 $x_1, \cdots , x_n$ で，$ \forall i, x_i \neq i$ となるものを完全順列といいます． また，その組み合わせの総数をモンモール数といいます． $n$ 番目のモンモール数 $a_n$ は以下の漸化式及び一般項で求まります．

\[\begin{eqnarray} a_1 &=& 0 \\ a_2 &=& 1 \\ a_n &=& (n-1)(a_{n-1}+a_{n-2}) \quad (n \ge 3) \end{eqnarray}\] \[a_n=\sum_{k=2}^n{\frac{(-1)^k n!}{k!}} \quad (n \ge 2)\]

一般項を $n!$ で割るとランダムな順列が完全順列になる確率となり，その極限は $\frac{1}{e} \simeq 0.36788$ となります．