インテジャーズ

INTEGERS

数、特に整数に関する記事。

完全順列とMontmort数

n個の元の順列を考えるとき、どの元(げん)をとっても元(もと)の位置にいないような順列のことを完全順列といいます。n個の元の完全順列の総数をD_nと表し、Montmort数と名付けられています。便宜的にD_0=1と定義します。

例えば、(1, 2, 3)の順列は

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

6通りですが、完全順列は

(2, 3, 1), (3, 1, 2)

の二通りです。

Montmort数は漸化式
D_m=(m-1)(D_{m-1}+D_{m-2})
を満たす。

証明. (1, 2, \dots, m)の完全順列を考える。完全順列においてm番目にくる数は1からm-1m-1通りある。m番目の数がkであったとしよう。もし、k番目の数がmであれば、残りの部分の順列の総数はD_{m-2}である。また、k番目がmでなければ、そのような順列の総数はD_{m-1}通りあることがわかる(mkを同一視していると考えればよい)。 Q.E.D.

この漸化式からD_nは明示的な表示

\displaystyle \frac{D_n}{n!} = \sum_{k=0}^n\frac{(-1)^k}{k!}

をもつことを(帰納法などで)示せます。また、この式から別の漸化式

D_m=mD_{m-1}+(-1)^m

を満たすことも分かります。Eulerはこれらの漸化式を証明していたそうです(流石!)。

演習問題 n \geq 2とする。このとき、D_nn-1の倍数であることを示せ。

つまり、D_nの絶対値が素数になるのは残念ながらD_3=2のみです。

順列を固定する元を指定しながら数えていくことによって、

\displaystyle n!=\sum_{k=0}^{n}\binom{n}{k}D_k

が成り立つことも分かります。

D_nの数値(n=0 \sim 50)

D_{0}= 1
D_{1}= 0
D_{2}= 1
D_{3}= 2
D_{4}= 9
D_{5}= 44
D_{6}= 265
D_{7}= 1854
D_{8}= 14833
D_{9}= 133496
D_{10}= 1334961
D_{11}= 14684570
D_{12}= 176214841
D_{13}= 2290792932
D_{14}= 32071101049
D_{15}= 481066515734
D_{16}= 7697064251745
D_{17}= 130850092279664
D_{18}= 2355301661033953
D_{19}= 44750731559645106
D_{20}= 895014631192902121
D_{21}= 18795307255050944540
D_{22}= 413496759611120779881
D_{23}= 9510425471055777937262
D_{24}= 228250211305338670494289
D_{25}= 5706255282633466762357224
D_{26}= 148362637348470135821287825
D_{27}= 4005791208408693667174771274
D_{28}= 112162153835443422680893595673
D_{29}= 3252702461227859257745914274516
D_{30}= 97581073836835777732377428235481
D_{31}= 3025013288941909109703700275299910
D_{32}= 96800425246141091510518408809597121
D_{33}= 3194414033122656019847107490716704992
D_{34}= 108610077126170304674801654684367969729
D_{35}= 3801352699415960663618057913952878940514
D_{36}= 136848697178974583890250084902303641858505
D_{37}= 5063401795622059603939253141385234748764684
D_{38}= 192409268233638264949691619372638920453057993
D_{39}= 7503961461111892333037973155532917897669261726
D_{40}= 300158458444475693321518926221316715906770469041
D_{41}= 12306496796223503426182275975073985352177589230680
D_{42}= 516872865441387143899655590953107384791458747688561
D_{43}= 22225533213979647187685190410983617546032726150608122
D_{44}= 977923461415104476258148378083279172025439950626757369
D_{45}= 44006555763679701431616677013747562741144797778204081604
D_{46}= 2024301565129266265854367142632387886092660697797387753785
D_{47}= 95142173561075514495155255703722230646355052796477224427894
D_{48}= 4566824330931624695767452273778667071025042534230906772538913
D_{49}= 223774392215649610092605161415154686480227084177314431854406736
D_{50}= 11188719610782480504630258070757734324011354208865721592720336801

私はなんとなくD_7=1854を気に入ってます。