ホーム > libalgo

モンモール数

説明

$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$ となります.