完全順列の漸化式

質問

完全順列をウィキペディアで調べると以下のように漸化式について解説していました。

モンモール数Ａnを与える漸化式を考える。
n番目に置く数の選び方は1からn-1までの(n-1)通りである。ここで選んだ数をiとする。
次にi番目がnかどうかで場合分けをする。
ｉ番目がnであれば、i番目に置かれたnとn番目に置かれたiを除く（n-2）個の数の並べ方の
総数は、(n-2)個の数による完全順列の数、すなわちA(n-2)に等しい。
i番目がnでない場合は、n番目に置かれたiを除く(n-1)個の数の並べ方の総数は、(n-1)個
の数による完全順列の数、すなわちA(n-1)となる。
以上をまとめると下の漸化式が得られる。

　An=(n-1)・{A(n-1)＋A(n-2)｝　　　n>=3

これでは訳が解らないのでn=4の場合を考えます。
4番目に置く数の選び方は1から(4-1)までの3通りである。ここで選んだ数ｉは3である。
次に3番目(i番目)が4(n)かどうかで場合分けをする。
3番目(i番目)が4（n）であれば3(i)番目に置かれた4（n）と4(n)番目に置かれた3(i)を除く(4-2）個
の数の並べ方の総数は、(4-2)個の数による完全順列の数、すなわちA(4-2)に等しい。
3(i)番目が4(n)でない場合は4(n)番目に置かれた3(i)を除く(4-1)個の数の並べ方の総数は
(4-1)個の数による完全順列の数、すなわちA(4-1)となる。

　A4=(4-1)・{A(4-1)＋A(4-2)}=3×(A3＋A2)

　両辺をそれぞれ自力で強引に調べると確かに両辺とも9になっていて
　この漸化式は正しいようですが、n=4の場合に簡単化してもいまひとつ
　ピンときません。
　平たく云って、この漸化式はどのような考え方に基づいて成り立って
　いるのでしょうか。

回答No.1

naniwacchi · ベストアンサー

こんばんわ。

質問の内容では「n個の数をどのように配置するか（並べるか）」を考えています。

＞n番目に置く数の選び方は1からn-1までの(n-1)通りである。ここで選んだ数をiとする。
※「ｉ」は見づらいので、以下 pと表すことにします。
これは「座席番号：nの席には 1～n-1さんが座ることができる。
そこで、pさんを座席番号：nに座らせた」ということを表しています。

このとき、「座席番号：pに誰が座るか」で場合分けがでてきます。

1) もし座席番号：pに nさんが座っていると、
残りの n-2個の座席は、その n-2個だけで完全順列になるよう座っていればよいことになります。
⇒ この並び方は A(n-2)とおり

2) 座席番号：pに nさんが座っていないとき、
座席番号：1～n-1には pさんを除いた 1～nさんたちが座ることになります。
この n-1人が完全順列になっていればよいことになります。
⇒ この並び方は A(n-1)とおり

1)、2)は最初の pの選び方の数だけ選択肢がでてくるので、
その選び方 n-1とおりごとに考えることになります。
ということで
A(n)＝ (n-1){ A(n-2)+ A(n-1) }

となります。

逆に、n個の完全順列に 1つ数を加える方針で考えた過去の質問がありますので、
参考までに。
http://okwave.jp/qa/q5416681.html

参考URL：

http://okwave.jp/qa/q5416681.html

お礼

ご回答ありがとうございました。
ご回答を拝読しても解らなかったので、しばらく頭の中で寝かせていました。
今日暫くぶりに読み返してみたら解りました。
次はnに＋1して証明する方法を勉強します。
プリントアウトしたので、また通勤電車の中で読ませていただきます。