完全順列

出典: フリー百科事典『ウィキペディア(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]
モンモール数の一覧表

モンモール数の一覧表
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番目に置かれた 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 (英語).

関連項目[編集]

参考文献[編集]

外部リンク[編集]