完全順列
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/29 01:31 UTC 版)
完全順列（かんぜんじゅんれつ、英: complete permutations）、もしくは攪乱順列（かくらんじゅんれつ、英: derangement）とは、整数 1, 2, 3, …, n を要素とする順列において、i 番目 (i ≦ n) が i でない順列である。順列を置換とみると、完全順列は不動点の個数が 0 の置換に対応している。乱列、混乱順列ともいう。
モンモール数
完全順列の総数をモンモール数 (英: Montmort number) という。モンモール数はしばしば !n と書かれる[1]。これはフランスの数学者 ピエール・モンモール に因んで名づけられた。
モンモール数を小さい順に並べると
である。
例
例えば 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]。
モンモール数の一覧表
| n | an |
|---|---|
| 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 |
漸化式
モンモール数 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となる。
以上をまとめると、以下の漸化式が得られる[2]。
完全順列と同じ種類の言葉
- 完全順列のページへのリンク
