すれちがい順列 - inamori’s diary

最近買った本

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

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!})$

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

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))

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

やっぱり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)ⁿ

というわけで、

D(n+1) = (n+1)D(n) + (-1)ⁿ⁺¹

D(n+1)/(n+1)! = D(n)/n! + (-1)ⁿ⁺¹/(n+1)!
= ... = D(2)/2! + (-1)ⁿ⁺¹/(n+1)!
+ ... + (-1)³/3!

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