小球入盒$\abs{i-j}\le 2$,糊涂了

realnumber

诸暨市2021年5月高三适应性考试 第16题
编号为i(i=1,2,3,4,5)的五个小球放入编号为j(j=1,2,3,4,5)的五个盒子，每盒一个小球，若满足$\abs{i-j}\le 2$,则不同的放法共有______种.

答案31，可以用分类穷举找出来.当问题推广到n球与盒时，......

试着找递推关系时，把自己整糊涂了.
$f(n)$表示n球n盒时的放法种数.
1.当1号球放在1号盒时（以下简化说成球1盒1），余下球放法有f(n-1)种.
2.当球1盒2，
---（2.1）.同时有球2盒1，有f(n-2)种；
---（2.2）若同时有球2盒3，此时盒1只能放3号球了，有f(n-3).
--- (2.3)若同时有球2盒4，此时盒1只能放3号球，
------（2.3.1）球4盒3，有f(n-4).
------（2.3.2）球5盒3,
---------(2.3.2.1)球4盒5，有f(n-5).
---------(2.3.2.2)球4盒6
------------（2.3.2.2.1）没完没了的，甩手不干了？？？？
3.当球1盒3，（3.1）球3盒1，有f(n-2);(3.2.1)球3盒2,球2盒1，f(n-3);(3.2.2)球3盒2，球2盒4，无，因为盒1没法放了

综上，f(n)=f(n-1)+2f(n-2)+2f(n-3)+f(n-4)+f(n-5)+...(此处省略号会出问题吗？),
又f(1)=1,f(2)=2,f(3)=6,f(4)=14,f(5)=31,f(k)=0,$k\le0$.

tommywong

oeis.org/A002524
Number of permutations of length n within distance 2 of a fixed permutation.

$f(n)=2f(n-1)+2f(n-3)-f(n-5)$

tommywong

f:XXX?????...
1,1,2,6,14,31,73
g:XXX?X???...
0,1,2,4,10,24,55

(2.3) 31?2???..., 有g(n-3)
(2.3.2.2) 3152?4???..., 有g(n-5)

(3.1) 3?1???..., 唔係f(n-2)
(3.1.1) 321???..., 有f(n-3)
(3.1.2) 3412???..., 有f(n-4)
(3.3) 2413???..., 有f(n-4)
(3.4) 241?3???..., 有g(n-4)

f(n)=f(n-1)+f(n-2)+3f(n-3)+2f(n-4)+g(n-3)+g(n-4)
g(n-3)=f(n-4)+f(n-5)+g(n-5)

f(n)=f(n-1)+f(n-2)+3f(n-3)+2f(n-4)+g(n-3)+g(n-4)
f(n-1)=f(n-2)+f(n-3)+3f(n-4)+2f(n-5)+g(n-4)+g(n-5)
f(n)-f(n-1)=f(n-1)+2f(n-3)-f(n-4)-2f(n-5)+g(n-3)-g(n-5)
f(n)=2f(n-1)+2f(n-3)-f(n-5)