>>425,431
f(n+1)通りの間違いのそれぞれについて
n+1個目がk番目の答えになっていたとして
n+1番目の答えがk個目の場合とそうで無い場合に分けて
k個目の場合はこの2つの答えを入れ替えたら両方正解になって
あとのn-1個は全部不正解のままつまりf(n-1)通り
k個目で無い場合はこの2つの答えを入れ替えたらn+1番目の答えは正解だけどk番目の答えは不正解のままつまりf(n)通り
kとしては1〜nまで考えられるから
f(n+1)=n(f(n-1)+f(n))
なおf(0)=1,f(1)=0
順に
1 0 1 2 9 44 265 …