撹乱順列とは
{1,2,3,...n}の順列で，どの要素も元の位置にないような順列を撹乱順列(またの名を完全順列)といいます．例えばn=3の撹乱順列として{2,3,1},{3,2,1},{3,1,2}とかが挙げられます．{2,1,3}とかは撹乱順列ではありません．3番目の要素が元の位置にあります．
つまり，{1,2,...n} の順列 P = {p1,p2,...,pn}について考えるとき，全ての i についてpi≠iが成り立つような順列を撹乱順列と呼びます．
そしてその撹乱順列の個数はモンモール数という名前がついており，以下の漸化式で求められます．
個数の漸化式
- a1 = 1
- a2 = 1
- an = (n-1)(an-1+an-2) (n ≧ 3)
なぜこのような漸化式になるのかについて考えてみましょう．説明のために遷移とかいう言葉を使っていますが再帰をイメージしてください．
まず，長さnの撹乱順列 {1,2,..,n}のうち，1の位置をiで確定させることを考えます(n-1通りあります)．別に確定させる数字のはnとかでも何でもいいですが，とりあえず1に着目してその位置を考えます．
確定としては，こんな感じですね．いま，位置 i が埋まってしまったのですが，数字 i はフリーです．これはちょっと厄介な状態です．
撹乱順列の漸化式は，ある使われてない数字の元の位置が既に埋まっているような状態に対する式ではありませんでした．
iをどこに置くか考えてみましょう．
数字 i の位置を 1 に行かせるケース
数字 i の位置を 1 に行かせるケースを考えます．
この場合，なんか明らかに残ったやつを再ラベリングすれば{1,2,...n-2}の撹乱順列を求めることと同等になるので，an-2に遷移したら良さそうな感じしますね．このケースはとても簡単でした．
数字 i の位置を 1以外 に行かせるケース
さて，もうひとつが厄介です．以下のような1じゃないところに遷移するケースです．
これ頭の良い人がグッと睨むと，長さn-1の撹乱順列と状態が等価らしいんですが，「は?」状態です．いやいや，下の図の2つの状態が等価てお前．
何言ってるのって気分になりました(図で本来 1 2 3 … i-1 i+1 … nとなるべきところが1 2 3 n とはしょられてるのはご愛嬌)．
いやだってさ，上の状態，数字1使われてるやん，しかも数字iの元の位置埋まってるのに数字iフリーじゃん．下の綺麗な状態と等価だなんてとても思えない．
ただ，よく見てみると「数字iの位置は1以外」という条件があります．これがキモっぽいです．
よく考えてみると，上の状態における数字iを数字1に再ラベルしても問題なさそうな感じがしませんか? だって，数字iを1にしたところで，「iの位置は1以外」という性質が「1の位置は1以外」と言い変わるだけで，その性質というのは常に撹乱順列だから元々成り立っているはずです．
この変換によって，上の状態が下の状態と等価な状態になり，長さn-1の撹乱順列の状態であることがわかりました．
まとめ
まとめると，iを選ぶ候補として(n-1)通りあって，あとはiを選ぶとそれぞれのiについてan-1+an-2通りだけ組み合わせの数があることが分かるので，冒頭で述べた漸化式になります．
参考にしたサイト
ちなみに，ほとんどこちら様の受け売りです．こちら様の素晴らしい親切な説明ですら少し悩んだので，悩んだ部分について皆さんと共有しようと思いました．
