完全順列

完全順列（かんぜんじゅんれつ、英: complete permutations）、もしくは攪乱順列（かくらんじゅんれつ、英: derangement）とは、整数 1, 2, 3, …, $n$ を要素とする順列において、 $i$ 番目 ( $i$ ≦ $n$ ) が $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$	$a n$
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

漸化式

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

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

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

a_{n}=(n-1)(a_{n-1}+a_{n-2}),\quad n\geqq 3

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

a_{n}=\sum _{k=0}^{n}{\frac {(-1)^{k}n!}{k!}},\quad n\geqq 0

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

a_{n}=na_{n-1}+(-1)^{n},\quad n\geqq 1

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

{\frac {a_{n}}{n!}}=\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}},\quad n\geqq 0

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

e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}

に $x$ = -1 を代入した式になっているので、自然対数の底 $e$ の逆数 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/e$ となる^[2]。パーセントで表すとおよそ36.788%である。

具体例

例えば 5 人でプレゼントを持ち寄ってランダムに分け直したとき、誰かが自分の持ってきたプレゼントに当たってしまう確率 $p 5$ は

p_{5}={\dfrac {5!-44}{5!}}={\dfrac {76}{120}}={\dfrac {19}{30}}=0.6333\cdots

となる。

人数が 10 人の場合の確率 $p$ ₁₀ は

p_{10}={\dfrac {10!-1334961}{10!}}={\dfrac {2293839}{3628800}}=0.63212053571428571428571428571429\cdots

となる。

人数が $n$ 人の場合の確率 $p$ _$n$ の極限は

\lim _{n\to \infty }p_{n}=1-{\frac {1}{e}}=0.63212055882855767840447622983854\cdots

となる。

上記の式におけるの $n$ 人のときの分子の数 $(n! - a n)$ はオンライン整数列大辞典の数列 A002467を参照。

包除原理による解法

包除原理を用いてもモンモール数の一般項を求めることができる。 $1 ≦ k ≦ n$ を満たす自然数 $k$ に対して、集合 $A_{k}$ を $n$ 個の数字 ${1, 2, \dots, n}$ を自分自身に写す置換の中で、 $k$ 番目の数字を固定する（すなわち、 $k$ を $k$ に写した）順列の集合とする。 $i$ 個の集合の共通部分は $i$ 個の数字を固定する置換を施した順列になるので、その元の個数は $(n-i)!$ に等しくなる。このとき、共通部分の選び方は $_{n}\mathrm {C} _{i}={\tbinom {n}{i}}$ 通りになるので、包除原理により以下の式が成り立つ。

{\begin{aligned}|A_{1}\cup \cdots \cup A_{n}|&=\sum _{i}\left|A_{i}\right|-\sum _{i<j}\left|A_{i}\cap A_{j}\right|+\sum _{i<j<k}\left|A_{i}\cap A_{j}\cap A_{k}\right|+\cdots +(-1)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|\\&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-\cdots +(-1)^{n+1}{n \choose n}0!\\&=\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}(n-i)!\\&=n!\ \sum _{i=1}^{n}{(-1)^{i+1} \over i!}\end{aligned}}

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

a_{n}=n!-|A_{1}\cup \cdots \cup A_{n}|=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}.

母関数

モンモール数 $a$ _$n$を与える母関数は以下のようになる^[1]。

{\begin{aligned}\sum _{n=0}^{\infty }a_{n}x^{n}&={\frac {e^{-\left(1+{\frac {1}{x}}\right)}}{x}}\mathrm {Ei} \left(1+{\frac {1}{x}}\right)\\&=1+x^{2}+2x^{3}+9x^{4}+44x^{5}+265x^{6}+\cdots \end{aligned}}

ここで、 $Ei$ は指数積分である。また、指数型母関数は以下のようになる^[1]。

{\begin{aligned}\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}&={\frac {e^{-x}}{1-x}}\\&=1+{\frac {1}{2}}x^{2}+{\frac {1}{3}}x^{3}+{\frac {3}{8}}x^{4}+{\frac {11}{30}}x^{5}+{\frac {53}{144}}x^{6}+\cdots \end{aligned}}

ここで、係数の分子の列はオンライン整数列大辞典の数列 A053557を参照、分母の列はオンライン整数列大辞典の数列 A053556を参照。

計算式

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

a_{n}=\left\lfloor {\frac {n!}{e}}\right\rceil ,\quad n\geqq 1

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

a_{n}=\left\lfloor {\frac {n!+1}{e}}\right\rfloor ,\quad n\geqq 1

ここで、 $⌊ x ⌋$ は床関数の値である^[1]。

積分表示

モンモール数は不完全ガンマ関数 $Γ(a, x)$ を用いて以下のように表される^[1]。

a_{n}={\frac {\Gamma (n+1,-1)}{e}}.

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

a_{n}=\int _{-1}^{\infty }x^{n}e^{-(x+1)}dx=\int _{0}^{\infty }(x-1)^{n}e^{-x}dx.

連分数

以下のような連分数が得られる^[1]。

a_{n}={\frac {n!}{e}}+{\cfrac {(-1)^{n}}{n+2-{\cfrac {1}{n+3-{\cfrac {2}{n+4-{\cfrac {3}{n+5-\ddots }}}}}}}}

脚注

[脚注の使い方]

^ ^a ^b ^c ^d ^e ^f Weisstein, Eric W. "Subfactorial". mathworld.wolfram.com (英語).
^ ^a ^b ^c ^d ^e Weisstein, Eric W. "Derangement". mathworld.wolfram.com (英語).

参考文献

Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994), Concrete Mathematics (2nd ed.), Addison-Wesley, Reading MA, ISBN 978-0-201-55802-9
- ロナルド・L・グレアム、ドナルド・E・クヌース、オーレン・パタシュニク著、有澤誠ほか訳『コンピュータの数学』（第2版）共立出版、2020年9月。ISBN 978-4-320-12464-6。

外部リンク

『攪乱順列（完全順列）の個数を求める公式』 - 高校数学の美しい物語
『モンモールの問題の応用』 - 高校数学の美しい物語
完全順列とモンモール数
Baez, John (2003), Let's get deranged! 2012年10月11日閲覧。
Bogart, Kenneth P.; Doyle, Peter G. (1985), Non-sexist solution of the ménage problem 2012年10月11日閲覧。
Dickau, Robert M., “Derangement diagrams”, Mathematical Figures Using Mathematica 2012-10-11閲覧。
Hassani, Mehdi, Derangements and Applications, Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003 2012年10月11日閲覧。
Weisstein, Eric W. "Derangement". mathworld.wolfram.com (英語).

[Mathworld-Subfactorial-1] ^ ^a ^b ^c ^d ^e ^f Weisstein, Eric W. "Subfactorial". mathworld.wolfram.com (英語).

[Mathworld-Derangement-2] Weisstein, Eric W. "Derangement". mathworld.wolfram.com (英語).

[1]

[2]

モンモール数

例

漸化式

具体例

包除原理による解法

母関数

計算式

積分表示

連分数

脚注

関連項目

参考文献

外部リンク