完全順列の証明

赤チャートに完全順列の証明が載っていました

＜証明＞
n個の数の順列1,2,・・・,nの完全順列の個数をW(n)で表す。

1,2,・・・,nの完全順列をf(1),f(2),・・・f(n)とする。
f(1)=k とするとこの完全順列は[1],[2]のどちらかである。
[1]f(k)=1 であるもの
　1,k　を除いた　2,・・・,k-1,k+1,・・・,n のn-2個について完全順　列であるからその個数はW(n-2)個
[2]f=(k)　ではないもの　
　f(h)=1とするとh=kではないから,f(1)=1,f(h)=kと置き換えると,1を　除いた　2,・・・,n のn-1個について完全順列であるから,その個数
　はW(n-2)個

2≦k≦nであるから,kのとりうる値は　n-1通り
したがってW(n)=(n-1){W(N-1)+W(N-2)} 　　　＜終＞

いくつか理解できない点があります
(1)なぜf(k)=1と、f(k)=1でないものに分けて考えているのでしょうか？
(2)[2]で、f(1)=1,f(h)=kと置き換えるとはどういう事なのでしょうか？
　何のために置き換えるのですか？

No.3 ベストアンサー 回答者： naniwacchi 回答日時： 2009/11/02 22:16

#1です。

#2の方が着想について書かれていますが、
そのことで先の回答を書いているときに思ったことを書きます。

先の回答（質問者さんの回答でも）では、W(n)を W(n-1)と W(n-2)で表す方法を示しています。
以下では、逆に W(n)から出発して W(n+1)を表そうと考えてみます。

・すでに、W(n)で n個の数字が完全順列になっています。
そこへ数字「n+1」を付け足すことになります。
・付け足すだけだと「n+1」は n+1番目になってしまうので、どこかへ並べ直す必要があります。
そこで、先の n個のどれかと入れ換えることで実現します。（場合分けの[2]）

・ところが、先の n個の並びには f(k)＝kという場合がないので、その分が勘定から漏れてしまいます。
・そこで、f(k)＝kとなっているときの残り n-1個に対する完全順列を考えます。（場合分けの[1]）
結果、漸化式には W(n-1)も現れることになります。

この内容だと、W(n+1) = n* { W(n)+ W(n-1) }になります。

こう考えると、場合分けの[2]が一般的で、[1]が特殊な場合という感じになります。

注意深い考察がないと、なかなか導けない内容だと思います。
具体的に 3つ、4つぐらいの数字で、
さらに 1つを付け加えることを考えることで見えてくるように思います。

No.4 回答者： zk43 回答日時： 2009/11/02 22:25

何となく、チャートの解答は分かりにくいので、私なりの

理解の説明を・・・
（オイラーの本に載っていたものです。そもそも、この
漸化式を立てて最初にこの問題を解いたのもオイラーだそうです。）

1が2,3,…,nのどこに行くかはn-1通りある。
1がkに行くとする。ここに、k=2,3,…,nのどれかn-1通り。
ここで、kの行先で場合分けを行う。
(1)kが1に行く場合。
　後は、残りの2,3,…,k-1,k+1,…,nのn-2個で完全順列を
　作れば良いので、それは、W(n-2)通りある。
(2)kが1に行かない場合
　2が行ってはいけないのは2
　3が行ってはいけないのは3
　・・・
　k-1が行ってはいけないのはk-1
　kが行ってはいけないのは1
k+1が行ってはいけないのはk+1
　・・・
　nが行ってはいけないのはn
　となり、n-1個について、それぞれ行ってはいけない
　場所が1個あるので、これは、n-1個の完全順列に相当
　し、W(n-1)通りある。
　つまり、写像f：{2,3,…,n}→{1,2,…,k-1,k+1,…,n}
　で、禁止されているのは、
f(2)=2,f(3)=3,…,f(k)=1,…,f(n)=n
のどれかが成り立つ場合であり、右側の集合で、1がkの
　役割を果たしているということです。
そして、(1)と(2)は排反な事象で、kはn-1通り考えられるから、
W(n)=(n-1)W(n-2)+(n-1)W(n-1)となる。
完全順列というのは、2つの集合{a1,…,an}、{b1,…,bn}
の間の対応を考えるとき、a1→b1,…,an→bnとはならない
対応であるとも考えられます。
添え字で順番づけしていますが、要するにどの元も行っては
いけない場所が1か所あるということです。
実際例では、クラスで席替えを行ったとき、全員が元の自分
の席とは違う席になるのが完全順列です。
他にも、クラスでクリスマスプレゼントの交換を行うとき、
みんなが他の人のプレゼントをもらうというのも完全順列
です。

No.2 回答者： banakona 回答日時： 2009/11/02 21:59

（１）について、着想のことを聞いているのなら、これは「むかし、頭のいい人が、こう置くとウマく漸化式を立てられることを発見したから」としか言いようがないでしょう。

おそらく。

No.1 回答者： naniwacchi 回答日時： 2009/11/02 19:00

少し長くなりますが、容赦ください。

f(1)＝kとしたとき、kは 2～ nまでの n-1とおりを選ぶことができます。…(★)

f(2)～f(n)に入る数を考えると、1～ k-1と k+1～ nの n-1個となります。
つまり、kはすでに 1番目となっているので、2番目以降には絶対現れません。
つまり必然的に（自動的に）、f(k)≠kになるということです。

ここで完全順列の定義に戻ってみると、
「f(m)＝mとならないような並び方」を考えるということになります。
ここで、「何番目の数字」の集合と「並ぶ数字」の集合は
同じ要素が含まれていることが前提になっています。
これが重要なポイントです。

[1] f(k)＝1のとき
f(2)～ f(k-1)とf(k+1)～ f(n)に入る数は、
2～ k-1と k+1～ nと要素が一致しています。
つまり、n-2個の完全順列を考えていることになります。

[2] f(k)≠1のとき、
f(h)＝1とおくと
i＝ １, ２, …, ｈ, …, ｋ, …, ｎ
f(i)＝ｋ, □, …, １, …, ○, …, △
という並びになります。（表にするのがわかりやすいです）
このままではうまく要素が一致しません。

ここで、この f(i)の並び方を次のように考えます。
2～ nまでの n-1個の数を完全順列で並べてから、「ｋ」と書かれているところを「１」に入れ換えた。
先に完全順列で並べているので、f(k)＝○は kではありません。

すると、最後の入れ替えは「自動的に決まる」ので、
この組合せの数は W(n-1)とおりとなります。


あとは、[1]、[2]のそれぞれの場合について、kは n-1とおりの選択が可能であることから（★印）、

W(n)＝(n-1)* { W(n-2)+W(n-1) }

となります。

正直「完全順列」を知らなかったのですが、wikiなどの説明を参考にしました。
ポイントは、「要素をそろえないと完全順列として勘定できない」というところです。
わかりにくいところなどあれば、補足してください。