完全順列の一般項を導く - 倭算数理研究所

高校数学でもちらっと出てくる完全順列 (Derangement wikipedia:完全順列 ) の総数を導いてみます。　完全順列の定義は Wikipedia でも見てもらうことにして、イメージは「プレゼントを1人1個もちよってプレゼント交換したとき、全員が自分のプレゼントが当たらない交換の仕方」です。　n 人のプレゼント交換の場合の総数を ${ M_n }$ とおき（モンモール数と言うらしいので）、これの具体的な式を導きます。

樹形図

プレゼントを持ってくる人は大文字のアルファベット A, B, C, ... で表し、その人たちが持ってきたプレゼントを対応する小文字 a, b, c, ... で表すことにします。

高校数学でこの問題が出た場合は「頑張って樹形図を描こう！」となるので*1、まずは樹形図を。　ただし、後で漸化式を導く（というか説明する）ときのために、大文字（人）、小文字（プレゼント）ともにアルファベットの逆順に考えていきます（n = 2 以降の樹形図参照）。

n = 1 のとき

樹形図は

A
___
a （不適）

となり、プレゼントの交換の仕方は0通り。　まぁ、1人しかいないので自分のプレゼントしかないよね。　さみしい。　じ、自分へのご褒美だい！　ということで ${ M_1 = 0 }$ 。

n = 2 のとき

樹形図は（アルファベットを逆順に考えていくよ）

B   A
_____
a - b

まぁ、相手は一人しかいないし1通りだよね。　 ${ M_2 = 1 }$ 。

n = 3 のとき

樹形図は

C   B   A
_________
b - a - c
a - c - b

複数の場合が出てきたけど、まだ「樹」形図って感じではない。　 ${ M_3 = 2 }$ 。

n = 4 のとき

樹形図は

D   C   B   A
_____________
  / d - a - b
c - b - a - d
  \ a - d - b

  / d - a - c
b - a - d - c
      \ c - d

  / d - c - b
a - b - d - c
      \ c - d

おっ！　樹形図っぽくなってきた。 ${ M_4 = 9 }$ 。

n = 5 のとき

樹形図は

E   D   C   B   A
_________________
    e - b - a - c
  /   \ a - c - b

      / e - a - b
    c - b - a - e
  /   \ a - e - b
d
  \   / e - a - c
    b - a - e - c
          \ c - e 

  \   / e - c - b
    a - b - e - c
          \ c - e 

c ...

b ...

a ...

早々に描くのが面倒になってきたので「E = d」*2の場合だけ描いてるよ。　E にとっては a, b, c, d は同等なので、E = a, b, c の場合はそれぞれ E = d の場合の枝の数と同じになるね。　総数は ${ M_5 = 44 }$ 。

漸化式

さて、n = 5 までの樹形図を（自分の手で）描いてみると、漸化式の立て方がなんとなく分かってきます。

まず n = 4 のときの樹形図を考えてみましょう。　D にとって a, b, c は同等なので、D = c の場合の枝の数を数えて3倍すれば総数が求まります。　さらに D = c の場合を次の2つの場合に分けて考えます：

C = d のとき
C ≠ d のとき

まず「C = d」のとき。　この場合の樹形図を抜き出すと

[D = c, C = d]
D   C   B   A
_____________
  / d - a - b
c - ...
  \ ...

C, D 2人でプレゼント交換してるので、残りの A, B がプレゼント交換することになりますね。　つまり、A, B 2人の完全順列の数（ ${ M_2 = 1 }$ ）だけ枝の数があります。

次に「C ≠ d」のとき。　この場合の樹形図を抜き出すと

[D = c, C ≠ d]
D   C   B   A   |   C   B   A
_____________   |   _________
  / ...         |
c - b - a - d   |   b - a - c  
  \ a - d - b   |   a - c - b

右側に描いたのは A, B, C 3 人の樹形図です。　この2つの樹形図をじっと見比べると、左側の樹形図は（一番左の c を除いて）右側の樹形図で c → d に置き換えたものになっていることがわかります*3。　枝の数は ${ M_3 = 2 }$ 。　さてこれは何故かと考えると、プレゼント c は D がもらっているので、残りの A, B, C 3人でプレゼント a, b, d を分けることになるんですが、A ≠ a, B ≠ b であり、さらに今の場合 C ≠ d という条件でプレゼントを交換するので、これはまさに3人での完全順列となりますね。　おぉ！　ということで以下の式が成り立ちます。

　　 ${ \displaystyle M_4 = 3(M_3 + M_2) }$

具体的に値を代入して計算してみると

　　 ${ \displaystyle M_4 = 3(2 + 1) = 9 }$

となり、たしかにあってそうです。

さすがに n = 4 の場合だけでは不安なので、n = 5 の場合もそうなっているか確認しておきましょう。　「E = d」の場合の樹形図を考えて（全体はこれの4倍）、「D = e」の場合の樹形図を抜き出すと

E   D   C   B   A
_________________
    e - b - a - c
  /   \ a - c - b
d ...

C, B, A の部分はこの3人での完全順列になってますね。　同様に「D ≠ e」の場合の樹形図を抜き出すと

E   D   C   B   A
_________________
  / ...

      / e - a - b
    c - b - a - e
  /   \ a - e - b
d
  \   / e - a - c
    b - a - e - c
          \ c - e 

  \   / e - c - b
    a - b - e - c
          \ c - e

ちょっと隣に対応する n = 4 の場合の樹形図を描くのは面倒なのでしませんが、たしかに（一番左の d を除いて） n = 4 の場合の樹形図で d → e の置き換えを行った樹形図になってます。

以上を踏まえて

　　 ${ \displaystyle M_5 = 4(M_4 + M_3) = 44 }$

${ M_n }$ が満たす初項2項と漸化式は以下のように類推できますね（証明は上記の話を分かりにくく説明するだけになるので略）：

　　 ${ \displaystyle \begin{align*} M_1 &= 0 \\ M_2 &= 1 \\ M_n &= (n-1)\left(M_{n-1} + M_{n-2}\right) \qquad (n \ge 3) \end{align*} }$

一般項

では、上記の $ M_n $ の隣接3項間の漸化式を解いてみましょう。　解き方はいろいろあるかと思います。

隣接3項間 → 隣接2項間

まず漸化式を以下のように変形：

　　 ${ \displaystyle M_n - nM_{n-1} = -\left\{M_{n-1} - (n-1)M_{n-2}\right\} }$

ここで ${ a_n = M_{n+1} - (n+1)M_n }$ とおくと、初項と漸化式は

　　 ${ \displaystyle \begin{align*} a_1 \; &= M_2 - 2M_1 = 1 \\ a_{n+1} &= -a_n \qquad (n \ge 1) \end{align*} }$

この一般項は簡単に分かって ${ a_n = (-1)^{n-1} }$ となります。　これを ${ a_n }$ の定義式に入れ直すと

　　 ${ \displaystyle M_{n+1} - (n+1)M_n = (-1)^{n-1} }$

となり、 ${ M_n }$ の隣接2項間の漸化式になりました。

${ M_n }$ の一般項

上記の隣接2項間の漸化式の両辺を ${ (n+1)! }$ で割ると

　　 ${ \displaystyle \frac{M_{n+1}}{(n+1)!} - \frac{M_n}{n!} = \frac{(-1)^{n+1}}{(n+1)!} \qquad (\because (-1)^2 = 1) }$

ここで ${ b_n = \frac{M_n}{n!} }$ とおくと、初項と漸化式は

　　 ${ \displaystyle \begin{align*} b_1 &= M_1 = 0 \\ b_{n+1} &- b_n = \frac{(-1)^{n+1}}{(n+1)!} \end{align*} }$

よって ${ b_n }$ の一般項は（ ${ n \ge 2 }$ のとき）

　　 ${ \displaystyle \begin{align*} b_n &= b_1 + \sum_{k=2}^{n}(b_k - b_{k-1}) \\ &= \sum_{k=2}^n \frac{(-1)^k}{k!} \end{align*} }$

よって

　　 ${ \displaystyle \begin{align*} M_n & = n! \sum_{k=2}^n \frac{(-1)^k}{k!} \\ &= \sum_{k=2}^n \frac{(-1)^k n!}{k!} \\ &\left(= \sum_{k=2}^n (-1)^k {}_nP_{n-k}\right) \end{align*} }$

まとめると

　　 ${ \displaystyle \begin{align*} M_n = \begin{cases} 0 & (n = 1) \\[4mm] \displaystyle{ \sum_{k=2}^n \frac{(-1)^k n!}{k!} } \left(= \sum_{k=2}^n (-1)^k {}_nP_{n-k}\right)& (n \ge 2) \end{cases} \end{align*} }$

最初の数項

　　 ${ \displaystyle \begin{align*} M_2 &= \frac{(-1)^2 \cdot 2!}{2!} \\ &= 1 \end{align*} }$

　　 ${ \displaystyle \begin{align*} M_3 &= \frac{(-1)^2 \cdot 3!}{2!} + \frac{(-1)^3\cdot 3!}{3!} \\ &= 3 - 1\\ &= 2 \end{align*} }$

　　 ${ \displaystyle \begin{align*} M_4 &= \frac{(-1)^2 \cdot 4!}{2!} + \frac{(-1)^3\cdot 4!}{3!} + \frac{(-1)^4\cdot 4!}{4!} \\ &= 4 \cdot 3 - 4 + 1\\ &= 9 \end{align*} }$

　　 ${ \displaystyle \begin{align*} M_5 &= \frac{(-1)^2 \cdot 5!}{2!} + \frac{(-1)^3\cdot 5!}{3!} + \frac{(-1)^4\cdot 5!}{4!} + \frac{(-1)^5\cdot 5!}{5!} \\ &= 5 \cdot 4 \cdot 3 - 5 \cdot 4 + 5 - 1\\ &= 44 \end{align*} }$
一般項求めても計算はちょっと面倒だけど、確かに樹形図で求めた値と一致しますね。