メインメニューを開く

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

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

モンモール数編集

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

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

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通りになる。

漸化式編集

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

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

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

 

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

 

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

 

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

 

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

具体例編集

  • 例えば5人でプレゼントを持ち寄ってランダムに分け直したとき、誰かが自分の持ってきたプレゼントに当たってしまう確率 p
  となる。
上記の式における n 人のときの分子の数 n ! - (モンモール数) はオンライン整数列大辞典の数列 A002467を参照。

注釈編集

関連項目編集

参考文献編集

  • 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”. Mathematical 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日閲覧。
  • ドナルド・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 

外部リンク編集