完全順列
出典: フリー百科事典『ウィキペディア（Wikipedia）』
完全順列（かんぜんじゅんれつ）とは、整数{1,2,3,…,n}を要素とする順列において、i番目(i≦n)がiでない順列のことであり、その総数をモンモール数(Montmort number)という。これはフランスの数学者Pierre Raymond de Montmortにちなんで名づけられた。例えば{1,2,3,…,n}の要素を並べるとき、1番左端には1以外の数字が来るように、左から2番目には2以外の数字が来るように、同様に左からn番目にはn以外の数字が来るように並び替える。要素が{1}のとき完全順列はなし、要素が{1,2}のとき完全順列は(2,1)の1通り、要素が{1,2,3}のとき完全順列は(2,3,1)と(3,1,2)の2通りになる。
また、順列をｎ次対称群の置換とみると、完全順列は不動点の個数が0の置換に対応している。
目次 |
[編集] 漸化式
モンモール数anを与える漸化式を考えてみる。
n番目に置く数の選び方は1からn-1までの(n-1)通りである。ここで選んだ数をiとする。次に、i番目がnかどうかで場合分けをする。i番目がnであれば、i番目に置かれたnとn番目に置かれたiを除く(n-2)個の数の並べ方の総数は、(n-2)個の数による完全順列の数、すなわちan-2に等しい。i番目がnでない場合は、n番目に置かれたiを除く(n-1)個の数の並べ方の総数は、(n-1)個の数による完全順列の数、すなわちan-1となる。
以上をまとめると、下の漸化式が得られる。
a1 = 0、a2 = 1は容易にわかるので、この条件の下で漸化式を解くと、
となる。また、n個のものを並び替える順列をランダムに作ったとき完全順列になる確率は、この式の両辺をn!で割った
で表される。さらにnを無限大に近づけると
となり、この式は指数関数exをマクローリン展開した
の両辺にx = − 1を代入した式になっているので、自然対数の底eの逆数に近づく。パーセントで表すとおよそ37%である。
[編集] 最初の10項
0,1,2,9,44,265,1854,14833,133496,1334961
