東京工業大学２００４年後期数学第１問（解答・解説）
有名な攪乱順列（完全順列）の問題です。
（１）
２１４３ ３１４２ ４１２３
２３４１ ３４１２ ４３１２
２４１３ ３４２１ ４３２１
全部で９通りあります。
（２）
最初、場所１、場所２、・・・、場所ｎに並んでいたｎ個のものをそれぞれ単に１、２、・・・、ｎと表記します。
Ｄ（ｎ）について考えるとき、場所１に☆（２、３、・・・、ｎ）が来ることになりますが、この場合は次の２つの場合に分類することができます。
（あ）場所☆に１が来る場合
（い）場所☆以外に１が来る場合
（あ）の場合
場所１と場所☆については並べ方が決まっているので、残りの（ｎ−２）個の場所に問題の並べ方をすることになります。
場所１にどの整数が来るかで（ｎ−１）通りあるから、この場合の並べ方の総数は（ｎ−１）×Ｄ（ｎー２）通りあります。
（い）の場合
場所☆に１が来ないという条件は、場所☆に特定の１つの整数が来ないということに過ぎないから、場所１以外の（ｎ−１）個の場所に問題の並べ方をすることになります。
場所１にどの数が来るかで（ｎ−１）通りあるから、この場合の並べ方の総数は（ｎ−１）×Ｄ（ｎー１）通りあります。
したがって、
Ｄ（ｎ）
＝（ｎ−１）×Ｄ（ｎ−２）＋（ｎ−１）×Ｄ（ｎー１）
＝（ｎ−１）×｛Ｄ（ｎ−２）＋Ｄ（ｎー１）｝
となります。
具体的に計算してみると、ｎ（２）＝１通り、ｎ（３）＝２通りだから、
ｎ（４）＝（４−１）×（２＋１）＝９通り
ｎ（５）＝（５−１）×（９＋２）＝４４通り
ｎ（６）＝（６−１）×（４４＋９）＝２６５通り
となります。
なお、ｎ（１）＝０と考えることができるので、ｎ（３）＝（３−１）×（１＋０）＝２とすることができますね。