読者です 読者をやめる 読者になる 読者になる

倭算数理研究所

科学・数学・学習関連の記事を、「倭マン日記」とは別に書いていくのだ!

完全順列の一般項を導く

高校数学でもちらっと出てくる完全順列 (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*}
}
一般項求めても計算はちょっと面倒だけど、確かに樹形図で求めた値と一致しますね。

追記【コメントへの解答】
 { a_n } を上記のように定義すると、 { n \geqq 3 } のとき

  { \displaystyle\begin{align*}
  a_{n-1} &= M_n -nM_{n-1} \\
  a_{n-2} &= M_{n-1} - (n-1)M_{n-2}
\end{align*}}

となります。  { M_n } の隣接3項間の漸化式は

  { \displaystyle\begin{align*}
  a_{n−1} = −a_{n−2} \qquad(n \geqq 3)
\end{align*}}

と書き換えられます。 ここで  { n } { n+2 } を代入し直すと  { a_{n+1}=−a_n\;(n \geqq 1) } となります。

もしくは  {  M_n } の漸化式の方で先に  { n } を2つ増しした方が分かりやすいかもしれません。

Javaによるアルゴリズム事典

Javaによるアルゴリズム事典

*1:ハイレベルな参考書では漸化式の説明があるけど。

*2:この「=」の意味は雰囲気で読み取ってね。 後で出てくる「≠」はこれの否定。

*3:樹形図を描くときにアルファベットの逆順に描いたのは、この置き換えだけで同じものだとわかるようにするためです。 アルファベット順に描くと他の文字(プレゼント)も置き換えしないと同じ樹形図だということがわかりにくいです。 実際描いてみると分かる(分かりにくい?)と思います。