完全順列

完全順列（かんぜんじゅんれつ、英 Derangement）、もしくは攪乱順列（かくらんじゅんれつ）とは、整数 1, 2, 3, …, n を要素とする順列において、i 番目 (i ≤ n) が i でない順列である。

順列を置換とみると、完全順列は不動点の個数が0の置換に対応している。

モンモール数

完全順列の総数をモンモール数 (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通りになる。

漸化式

モンモール数 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）

である。

参考文献

• Baez, John (2003年). “Let's get deranged!”. 2012年10月11日閲覧。
• Bogart, Kenneth P. and Doyle, Peter G. (1985年). “Non-sexist solution of the ménage problem”. 2012年10月11日閲覧。
• Dickau, Robert M.. “Derangement diagrams”. Figures Using Mathematica. 2012年10月11日閲覧。
• Hassani, Mehdi. “Derangements and Applications”. Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003. 2012年10月11日閲覧。
• Weisstein, Eric W. “Derangement”. MathWorld–A Wolfram Web Resource. 2012年10月11日閲覧。
• Debra K. Borkovitz. “Derangements and the Inclusion-Exclusion Principle”. Articles, Associate Professor of Mathematics, Wheelock College. 2012年10月11日閲覧。

外部リンク

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