完全順列が分かりません

質問

完全順列を青チャートで学んでいるんですが、
公式Ｗ（ｎ）＝（n-1）{W(n-1)+W(n-2)}の意味がさっぱりわかりません。
ご説明できる方、助けてください。よろしくお願いします。

回答No.2

Ae610

完全順列の定義：整数{1,2,3,…,n}を要素とする順列において、i番目(i≦n)がiでない順列のこと(ウィキペディアより引用)
例えば、{1}ならば完全順列はない。,{1,2}ならば完全順列は(2,1)の1通りのみ、{1,2,3}ならば完全順列は(2,3,1)(3,1,2)の2通り、{1,2,3,4}ならば1が1の位置以外にある場合の数は、2の位置または3の位置または4の位置の3通り。仮に1が2の位置にあった場合に、2が1の位置にある場合と無い場合に分けて考える。
2が1の位置にある場合：残りの(3,4)の2数の完全順列の数W(2)通り
2が1の位置にない場合：残りの2,3,4の3数の完全順列の数W(3)通り
1が3の位置および4の位置の時も同様。
従って4数の完全順列の数W(4)は、W(4)=(4-1){W(3)+W(2)}通り
{1,2,3,4,5}の場合は、(要素の名前をアルファベットに変えてありますが)ANo1様の回答の通り。（2項目の記号Wが抜けているようですが・・・）
{1,2,3,・・,i,・・・,n}ならばnの位置にくる数は1～n-1までの(n-1通り)
iの位置にnが来たとすると、nの位置がiである場合とi以外である場合とに分ける。
nの位置がiである場合：nとiを除いた(n-2)個の完全順列の数W(n-2)通り
nの位置がiでない場合：nを除く(n-1)個の完全順列の数W(n-1)通り
よって{1,2,3,・・・,n}のn個の数の完全順列の数W(n)は
W(n)=(n-1){W(n-1)+W(n-2)}通り

回答No.1

banakona

話を簡単にするためにｎ＝５で考えます。
Ａ、Ｂ、Ｃ、Ｄ、Ｅを並べ替えるとしましょう。
（１）Ａが２番目に来るとします。
　　　そして、そもそも２番目に来ることができなかったＢに着目します。
　　　（１－１）Ｂが一番目に来ない場合
　　　　　　　　　これはＢが一番目に来るのを許さないことになるので、
　　　　　　　　　ＢＣＤＥの４個の完全順列に等しい。よってＷ（４）通り。
　　　（１－２）Ｂが一番目に来る場合
　　　　　　　　　これは残りのＣＤＥの３個で完全順列を考えればいい。
　　　　　　　　　よってＷ（３）通り。
　　　　つまり、Ａが２番目に来る場合＝Ｗ（４）＋（３）

（２）Ａが３番目に来る場合は、Ｃ について同様に考えれば良く、
　　　　Ａが３番目に来る場合＝Ｗ（４）＋（３）
（３）Ａが４番目に来る場合も同じで、Ｗ（４）＋（３）
（４）Ａが５番目に来る場合も同じで、Ｗ（４）＋（３）

以上をまとめると　５個の完全順列Ｗ（５）＝４×｛Ｗ（４）＋（３）｝　・・・★

★を一般化すれば　Ｗ（ｎ）＝（ｎ－１）×｛Ｗ（n-1）＋（n-2）｝