選擇第6題
有
A、
B、
C、
D、
E五個觀光站,今規劃5天的觀光路線,每一天只觀光一站,且隔天必到另一站觀光,而每一站觀光次數不限。求第一天在
A站,第5天在
C站的觀光路線安排,共有幾種方法?(A)50 (B)51 (C)52 (D)53
[解答]
遞迴的做法
設
an是n天中,第一天在A,第n天在C的觀光路線安排方法數
易知
a2=1
a3=3
若第n天排C,第n+2天也排C,則第n+1天有4種排法
若第n+1天排C,則第n天排C以外的其中之一,此時在第n天和第n+1天之間可插入3種排法,變成n+2天的排法
故
an+2=4an+3an+1
\begin{align}
& {{a}_{n}}=\frac{{{4}^{n-1}}+{{\left( -1 \right)}^{n}}}{5} \\
& {{a}_{5}}=51 \\
\end{align}