完全順列

提供: miniwiki
移動先:案内検索

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

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

モンモール数

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

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

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 [1]を与える漸化式を考える。

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

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

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

a1 = 0, a2 = 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を参照。

注釈

  1. !nという書き方をする場合もある

関連項目

参考文献

外部リンク

fr:Analogues de la factorielle#Superfactorielle