每日一题[3188]递推计数

已知函数 $f:\{1,2, \cdots, 10\} \to\{1,2,3,4,5\}$，且对一切 $k=1,2, \cdots,9$，有 $|f(k+1)-f(k)| \geqslant 3$，则符合条件的函数 $f$ 的个数为_______．

答案    $288$．

解析    考虑由 $1,2,3,4,5$ 组成的 $n$ 项数列 $x_1,x_2,\cdots,x_n$，满足任意相邻两项的差的绝对值不小于 $3$ 的个数．设以 $1,2,4,5$ 结尾（符合要求的数列不可能出现 $3$）的数列分别有 $a_n,b_n,c_n,d_n$ 个，则 $$\begin{cases} a_{n+1}=c_n+d_n,\\ b_{n+1}=d_n,\\ c_{n+1}=a_n,\\ d_{n+1}=a_n+b_n,\end{cases}$$ 其中 $a_1=b_1=c_1=d_1=1$．设 $S_n=a_n+b_n+c_n+d_n$，则 $$a_{n+1}+d_{n+1}=S_n,\quad b_{n+1}+c_{n+1}=a_n+d_n=S_{n-1},$$ 从而 $$S_{n+1}=S_n+S_{n-1},$$ 其中 $S_1=4$，$S_2=6$．因此 $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}\hline n&1&2&3&4&5&6&7&8&9&10\\ \hline S_n&4&6&10&16&26&42&68&110&178&288\\ \hline\end{array}$$ 所求符合条件的函数 $f$ 的个数为 $S_{10}=288$．