完全順列

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
検索に移動

完全順列(かんぜんじゅんれつ、: complete permutations)、もしくは攪乱順列(かくらんじゅんれつ、: derangement)とは、整数 1, 2, 3, …, n を要素とする順列において、i 番目 (in) が i でない順列である。順列を置換とみると、完全順列は不動点の個数が 0 の置換に対応している。乱列、混乱順列ともいう。

モンモール数[編集]

完全順列の総数をモンモール数 (: Montmort number) という。モンモール数はしばしば !n とかかれる[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 通り。
  • n = 4 のとき完全順列は (2, 1, 4, 3), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 3, 1, 2), (4, 3, 2, 1) の 9 通りになる[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となる。

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

a1 = 0, a2 = 1#例のように計算できて、漸化式に n = 2 を代入して a0 = 1 が得られるので、この条件の下で漸化式を解くと、一般項は

となる。この一般項から、別の漸化式が得られる[2]

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

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

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

具体例[編集]

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

となる。

人数が 10 人の場合の確率 p10

となる。

人数が n 人の場合の確率 pn の極限は

となる。

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

包除原理による解法[編集]

包除原理を用いてもモンモール数の一般項を求めることができる。1 ≦ kn を満たす自然数 k に対して、集合 n 個の数字 {1, 2, …, n} を自分自身に写す置換の中で、k 番目の数字を固定する(すなわち、kk に写した)順列の集合とする。i 個の集合の共通部分は i 個の数字を固定する置換を施した順列になるので、その元の個数は に等しくなる。このとき、共通部分の選び方は 通りになるので、包除原理により以下の式が成り立つ。

このとき、完全順列は n 個の数字の中、どれも固定しない置換による順列になるので、以下の式を得る。

母関数[編集]

モンモール数 anを与える母関数は以下のようになる[1]

ここで、Ei指数積分である。また、指数型母関数は以下のようになる[1]

ここで、係数の分子の列はオンライン整数列大辞典の数列 A053557を参照、分母の列はオンライン整数列大辞典の数列 A053556を参照。

計算式[編集]

その他の計算式としては、以下のような式がある[2]

ここで、xx の小数点以下を四捨五入した値である。さらに、

ここで、x床関数の値である[1]

積分表示[編集]

モンモール数は不完全ガンマ関数 Γ(a, x) を用いて以下のように表される[1]

これは、不完全ガンマ関数の積分表示により以下のように表される。

連分数[編集]

以下のような連分数が得られる[1]

脚注[編集]

[脚注の使い方]
  1. ^ a b c d e f Weisstein, Eric W. "Subfactorial". MathWorld (英語).
  2. ^ a b c d e Weisstein, Eric W. "Derangement". MathWorld (英語).

関連項目[編集]

参考文献[編集]