完全順列

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

 モンモール数 
完全順列の総数をモンモール数 () という。モンモール数はしばしば  と書かれる。これはフランスの数学者  に因んで名づけられた。

モンモール数を小さい順に並べると
0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, …（）
である。

 例 
例えば 1, 2, 3, …,  の要素を並べるとき、1 番左端には 1 以外の数字が来るように、左から 2 番目には 2 以外の数字が来るように、同様に左から  番目には  以外の数字が来るように並べ替える。
 のとき完全順列はなし。
 のとき完全順列は  の 1 通り。
 のとき完全順列は  の 2 通り。
 のとき完全順列は  の 9 通りになる。

+ モンモール数の一覧表    0 1 1 0 2 1 3 2 4 9 5 44 6 265 7 1854 8 14833 9 133496 10 1334961 11 14684570 12 176214841 13 2290792932 14 32071101049 15 481066515734 16 7697064251745 17 130850092279664 18 2355301661033953 19 44750731559645106 20 895014631192902121 21 18795307255050944540 22 413496759611120779881 23 9510425471055777937262 24 228250211305338670494289 25 5706255282633466762357224 26 148362637348470135821287825 27 4005791208408693667174771274 28 112162153835443422680893595673 29 3252702461227859257745914274516 30 97581073836835777732377428235481 31 3025013288941909109703700275299910 32 96800425246141091510518408809597121 33 3194414033122656019847107490716704992 34 108610077126170304674801654684367969729 35 3801352699415960663618057913952878940514 36 136848697178974583890250084902303641858505 37 5063401795622059603939253141385234748764684 38 192409268233638264949691619372638920453057993 39 7503961461111892333037973155532917897669261726 40 300158458444475693321518926221316715906770469041 41 12306496796223503426182275975073985352177589230680 42 516872865441387143899655590953107384791458747688561 43 22225533213979647187685190410983617546032726150608122 44 977923461415104476258148378083279172025439950626757369 45 44006555763679701431616677013747562741144797778204081604 46 2024301565129266265854367142632387886092660697797387753785 47 95142173561075514495155255703722230646355052796477224427894 48 4566824330931624695767452273778667071025042534230906772538913 49 223774392215649610092605161415154686480227084177314431854406736 50 11188719610782480504630258070757734324011354208865721592720336801 51 570624700149906505736143161608644450524579064652151801228737176850 52 29672484407795138298279444403649511427278111361911893663894333196201 53 1572641673613142329808810553393424105645739902181330364186399659398652 54 84922650375109685809675769883244901704869954717791839666065581607527209 55 4670745770631032719532167343578469593767847509478551181633606988413996494 56 261561763155337832293801371240394297250999460530798866171481991351183803665 57 14909020499854256440746678160702474943306969250255535371774473507017476808904 58 864723188991546873563307333320743546711804216514821051562919463407013654916433 59 51018668150501265540235132665923869255996448774374442042212248341013805640069546 60 3061120089030075932414107959955432155359786926462466522532734900460828338404172761 61 186728325430834631877260585557281361476947002514210457874496828928110528642654538420 62 11577156176711747176390156304551444411570714155881048388218803393542852775844581382041 63 729360839132840072112579847186740997928954991820506048457784613793199724878208627068582 64 46679093704501764615205110219951423867453119476512387101298215282764782392205352132389249 65 3034141090792614699988332164296842551384452765973305161584383993379710855493347888605301184 66 200253311992312570199229922843591608391373882554238140664569343563060916462560960647949878145 67 13416971903484942203348404830520637762222050131133955424526146018725081402991584363412641835714 68 912354089436976069827691528475403367831099408917108968867777929273305535403427736712059644828553 69 62952432171151348818110715464802832380345859215280518851876677119858081942836513833132115493170156 70 4406670251980594417267750082536198266624210145069636319631367398390065735998555968319248084521910921 71 312873587890622203626010255860070076930318920299944178693827085285694667255897473750666614001055675390 72 22526898328124798661072738421925045538982962261595980865955550140570016042424618110047996208076008628081 73 1644463577953110302258309904800528324345756245096506603214755160261611171096997122033503723189548629849912 74 121690304768530162367114932955239096001585962137141488637891881859359226661177787030479275516026598608893489 75 9126772857639762177533619971642932200118947160285611647841891139451941999588334027285945663701994895667011674 76 693634737180621925492555117844862847209039984181706485235983726598347591968713386073731870441351612070692887225 77 53409874762907888262926744074054439235096078781991399363170746948072764581590930727677354023984074129443352316324 78 4165970231506815284508286037776246260337494144995329150327318261949675637364092596758833613870757782096581480673273 79 329111648289038407476154596984323454566662037454631002875858142694024375351763315143947855495789864785629936973188566 80 26328931863123072598092367758745876365332962996370480230068651415521950028141065211515828439663189182850394957855085281 81 2132643480912968880445481788458415985591970002706008898635560764657277952279426282132782103612718323810881991586261907760 82 174876765434863448196529506653590110818541540221892729688115982701896792086912955134888132496242902552492323310073476436321 83 14514771531093666200311949052247979197938947838417096564113626564257433743213775276195714997188160911856862834736098544214642 84 1219240808611867960826203720388830252626871618427036111385544631397624434429957123200440059763805516595976478117832277714029929 85 103635468732008776670227316233050571473284087566298069467771293668798076926546355472037405079923468910658000640015743605692543964 86 8912650310952754793639549196042349146702431530701633974228331255516634615682986570595216836873418326316588055041353950089558780905 87 775400577052889667046640780055684375763111543171042155757864819229947211564419831641783864807987394389543160788597793657791613938734 88 68235250780654290700104388644900225067153815799051709706692104092235354617668945184476980103102890706279798149396605841885662026608593 89 6072937319478231872309290589396120030976689606115602163895597264208946560972536121418451229176157272858902035296297919927823920368164776 90 546564358753040868507836153045650802787902064550404194750603753778805190487528250927660610625854154557301183176666812793504152833134829841 91 49737356646526719034213089927154223053699087874086781722304941593871272334365070834417115566952728064714407669076679964208877907815269515530 92 4575836811480458151147604273298188520940316084415983918452054626636157054761586516766374632159650981953725505555054556707216767519004795428761 93 425552823467682608056727197416731532447449395850686504416041080277162606092827546059272840790847541321696472016620073773771159379267445974874772 94 40001965405962165157332356557172764050060243209964531415107861546053284972725789329571647034339668884239468369562286934734488981651139921638228569 95 3800186713566405689946573872931412584755723104946630484435246846875062072408949986309306468262268544002749495108417258799776453256858292555631714054 96 364817924502374946234871091801415608136549418074876526505783697300005958951259198685693420953177780224263951530408056844778539512658396085340644549185 97 35387338676730369784782495904737313989245293553263023071061018638100578018272142272512261832458244681753603298449581513943518332727864420278042521270944 98 3467959190319576238908684598664256770946038768219776260963979826533856645790669942706201659580907978811853123248058988366464796607330713187248167084552513 99 343327959841638047651959775267761420323657838053757849835434002826851807933276324327913964298509889902373459201557839848280014864125740605537568541370698786

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

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

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

 は#例のように計算できて、漸化式に  を代入して  が得られるので、この条件の下で漸化式を解くと、一般項は

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

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

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

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

 具体例 
例えば 5 人でプレゼントを持ち寄ってランダムに分け直したとき、誰かが自分の持ってきたプレゼントに当たってしまう確率  は
 となる。
人数が 10 人の場合の確率 10 は
 となる。
人数が  人の場合の確率  の極限は
 となる。
上記の式におけるの  人のときの分子の数  はを参照。

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

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

 母関数 
モンモール数 を与える母関数は以下のようになる。

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

ここで、係数の分子の列はを参照、分母の列はを参照。

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

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

ここで、 は床関数の値である。

 積分表示 
モンモール数は不完全ガンマ関数  を用いて以下のように表される。

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

 連分数 
以下のような連分数が得られる。

 脚注 

 関連項目 

 階乗
 組合せ数学
 包除原理

 参考文献 



 外部リンク 


 完全順列とモンモール数






Category:順列
Category:不動点
Category:数学に関する記事