完全順列とモンモール数

$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)$

の六通りですが、完全順列は

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

の二通りです。

Montmort数は漸化式

$D_m=(m-1)(D_{m-1}+D_{m-2})$

を満たす。

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