20180203

0 以上の整数 n に対して S_{n} を 0 以上 n 未満の整数全体からなる集合とし, S_{n} を定義域とし, 各値が S_{n} の元である写像 f でどの S_{n} の元 x に対しても f(x)≠ x となるものの個数を a(n) とする.
n が 2 以上の整数ならば a(n)=(n-1)(a(n-1)+a(n-2)) が成り立つ.
この式から a(n)-na(n-1)=-(a(n-1)-(n-1)a((n-1)-1)) が分かる.
c=a(0)-a(1) とすると, 1 以上の整数 n に対して a(n)=na(n-1)+c(-1)^n が成り立つ.
a(1)=1*a(0)-c, a(2)=2*1*a(0)-2*c+c, a(3)=3*2*1*a(0)-3*2*c+3*c-c, a(4)=4*3*2*1*a(0)-4*3*2*c+4*3*c-4*c+c, a(5)=5*4*3*2*1*a(0)-5*4*3*2*c+5*4*3*c-5*4*c+5*c-c などが成り立つ.

a(n)=(n-1)(a(n-1)+a(n-2)) から a(n)-na(n-1)=-(a(n-1)-(n-1)a((n-1)-1)) にすることを思いつくには, 1, 0, 1, 2, 9, 44, 265, 1854, … を見てからになるだろう.