每日一题[1302]隐藏的斐波那契

设有 $10$ 个相同的红球和 $10$ 个相同的白球，从中任取 $10$ 个球排成一排，但红球不能相邻，则不同的排列方法数为_______．

答案    $144$．

解析    设从中任取 $k$ 个球排成一排的方法数为 $a_k$，则

$$a_2=3,a_3=5.$$ 而对于 $k+1$（$k\geqslant 3$）的情形，若第一个球为红球，则第二个球必然为白球，有 $a_{k-1}$ 种排法；若第一个球为白球，则有 $a_k$ 种排法．因此 $$a_{k+1}=a_k+a_{k-1},k\geqslant 3.$$ 进而有 $$\begin{array}{c|ccccccccc}\hline k&2&3&4&5&6&7&8&9&10\\ \hline a_k&3&5&8&13&21&34&55&89&144\\ \hline\end{array}$$