每日一题[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$.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复