完全順列

完全順列（かんぜんじゅんれつ）とは、整数 1, 2, 3, …, n を要素とする順列において、i 番目 (i ≤ n) が i でない順列のことであり、その総数をモンモール数 (Montmort number) という。これはフランスの数学者 Pierre Raymond de Montmort にちなんで名づけられた。例えば 1, 2, 3, …, n の要素を並べるとき、1番左端には1以外の数字が来るように、左から2番目には2以外の数字が来るように、同様に左から n 番目には n 以外の数字が来るように並び替える。n = 1 のとき完全順列はなし、n = 2 のとき完全順列は (2, 1) の1通り、n = 3 のとき完全順列は (2, 3, 1) と (3, 1, 2) の2通りになる。順列を置換とみると、完全順列は不動点の個数が0の置換に対応している。

漸化式

モンモール数 a_n を与える漸化式を考える。

n番目に置く数の選び方は 1 から n - 1 までの(n - 1)通りである。ここで選んだ数を i とする。次に、i番目が n かどうかで場合分けをする。i番目が n であれば、i番目に置かれた n とn番目に置かれた i を除く(n - 2)個の数の並べ方の総数は、(n - 2)個の数による完全順列の数、すなわち a_n-2に等しい。i番目が n でない場合は、n番目に置かれた i を除く(n - 1)個の数の並べ方の総数は、(n - 1)個の数による完全順列の数、すなわち a_n-1となる。

以上をまとめると、下の漸化式が得られる。

$a_n=(n-1)(a_{n-1}+a_{n-2}) ,\quad n \ge 3$

a₁ = 0, a₂ = 1 は容易にわかるので、この条件の下で漸化式を解くと、

$a_n=\sum_{k=2}^n{\frac{(-1)^k n!}{k!}} ,\quad n \ge 2$

となる。また、n個のものを並び替える順列をランダムに作ったとき完全順列になる確率は、この式の両辺を n! で割った

$\frac{a_n}{n!}=\sum_{k=2}^n{\frac{(-1)^k}{k!}} ,\quad n \ge 2$

で表される。さらに n → ∞ とすると、指数関数のマクローリン展開

$e^{x} = \sum^{\infin}_{n=0} \frac{x^n}{n!}$

に x = -1 を代入した式になっているので、自然対数の底 e の逆数となる。パーセントで表すとおよそ36.788%である。

モンモール数を小さい順に並べると

0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, …（オンライン整数列大辞典の数列 A166）

である。

外部リンク

• Weisstein, Eric W., "Derangement" - MathWorld.（英語）