すれちがい順列

最近買った本

数え上げ組合せ論入門 (日評数学選書)

数え上げ組合せ論入門 (日評数学選書)

を今日読んでいたら、
「すれちがい順列」なるものが載っていた。


1〜nを適当に並び替えたときに
元に戻る数字が一つもない場合の数、
なんだそうだ。
一言で表すと、
不動点の無い置換の数」ということになる。


例えばn=3なら、
「1->3、2->1、3->2」とか。
これを、


(3 1 2)


と表す。あと、
(2 3 1)
もあるから、
n次(1〜nのとき)の場合の数を
D(n)
と表すと、


D(3) = 2


また、


D(2) = 1


となる。

一般式

D(n)=n!(\sum_{k=0}^{n}(-1)^k\frac{1}{k!})


となるんだとか。
一応、後ろの方に求め方が載っているが、
たまに頭を使って考えてみよう。

漸化式(1)

D(4)を考えてみる。
一番右は1〜3になるが、
対称性からどれでも同じなので、
3として、あとから場合の数を3倍する。


4を3と考えると、
これで条件クリアならもちろんよいので、
この場合の数はD(3)。


あと、3を4で固定すれば、
残りの場合の数はD(2)。
まとめると、


D(4) = 3(D(3) + D(2))


一般化できて、


D(n+2) = (n+1)(D(n+1) + D(n))


あってんの?これ。
上の式当てはめたら、
確かに成り立つね。

漸化式(2)

やっぱり3つ項があるとつらいので、
2つにしないと。


D(n+2) - (n+2)D(n+1) = -(D(n+1) - (n+1)D(n))
= ... = (-1)n-1(D(3) - 3D(2))
= (-1)n

というわけで、


D(n+1) = (n+1)D(n) + (-1)n+1

漸化式を解く

D(n+1)/(n+1)! = D(n)/n! + (-1)n+1/(n+1)!
= ... = D(2)/2! + (-1)n+1/(n+1)!
+ ... + (-1)3/3!


うん、あってるね。
高校生でもできそうだ。