完全順列

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

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

モンモール数

完全順列の総数をモンモール数 (英: Montmort number) という。これはフランスの数学者 ピエール・モンモール にちなんで名づけられた。

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

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

である。

例

例えば 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となる。

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

[math]a_n=(n-1)(a_{n-1}+a_{n-2}) ,\quad n \ge 3[/math]

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

[math]a_n=\sum_{k=2}^n{\frac{(-1)^k n!}{k!}} ,\quad n \ge 2[/math]

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

[math]\frac{a_n}{n!}=\sum_{k=2}^n{\frac{(-1)^k}{k!}} ,\quad n \ge 2[/math]

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

[math]e^{x} = \sum^{\infin}_{n=0} \frac{x^n}{n!}[/math]

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

具体例

• 例えば5人でプレゼントを持ち寄ってランダムに分け直したとき、自分の持ってきたプレゼントに誰かが当たってしまう確率 p は

[math]p=\dfrac{5 !-44}{5 !}=\dfrac{76}{120}=\dfrac{19}{30}[/math] となる。

上記の式における n 人のときの分子の数 n ! - (モンモール数) はオンライン整数列大辞典の数列 A002467を参照。

関連項目

• 組合せ数学
• 包除原理
• 階乗

参考文献

• Baez, John (2003年). “Let's get deranged!”. . 2012閲覧.
• Bogart, Kenneth P. and Doyle, Peter G. (1985年). “Non-sexist solution of the ménage problem”. . 2012閲覧.
• Dickau, Robert M.. “Derangement diagrams”. Figures Using Mathematica. . 2012閲覧.
• Hassani, Mehdi. “Derangements and Applications”. Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003. . 2012閲覧.
• Weisstein, Eric W. “Derangement”. MathWorld–A Wolfram Web Resource. . 2012閲覧.
• Debra K. Borkovitz. “Derangements and the Inclusion-Exclusion Principle”. Articles, Associate Professor of Mathematics, Wheelock College. . 2012閲覧.
• ドナルド・E・クヌース、ロナルド・L・グレアム・オーレン・パタシュニク 『コンピュータの数学』 有澤誠・ほか訳、共立出版、1993年8月。ISBN 4-320-02668-3 : 原著 Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1988), Concrete Mathematics, Addison-Wesley, Reading MA, ISBN 0-201-14236-8 

外部リンク

• Weisstein, Eric W. “Derangement”. MathWorld（英語）.