在 A,B,C,D,E 中每天到一站，下一天必换一站，第一天是 A 第五天是 C 的路线有几种？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

luyuanhong

( 1) ABABC
( 2) ABADC
( 3) ABAEC
( 4) ABCAC
( 5) ABCBC
( 6) ABCDC
( 7) ABCEC
( 8) ABDAC
( 9) ABDBC
(10) ABDEC
(11) ABEAC
(12) ABEBC
(13) ABEDC
(14) ACABC
(15) ACADC
(16) ACAEC
(17) ACBAC
(18) ACBDC
(19) ACBEC
(20) ACDAC
(21) ACDBC
(22) ACDEC
(23) ACEAC
(24) ACEBC
(25) ACEDC
(26) ADABC
(27) ADADC
(28) ADAEC
(29) ADBAC
(30) ADBDC
(31) ADBEC
(32) ADCAC
(33) ADCBC
(34) ADCDC
(35) ADCEC
(36) ADEAC
(37) ADEBC
(38) ADEDC
(39) AEABC
(40) AEADC
(41) AEAEC
(42) AEBAC
(43) AEBDC
(44) AEBEC
(45) AECAC
(46) AECBC
(47) AECDC
(48) AECEC
(49) AEDAC
(50) AEDBC
(51) AEDEC

luyuanhong

题  有 A,B,C,D,E 五个观光点，每天观光一站，下一天必换另一站。

    问：第一天是 A 、第五天是 C 的观光路线有几种？

解  设 Xn 是长度为 n 、开头是 A 、末尾是 C 的观光路线数。
   
    设 Yn 是长度为 n 、开头是 A 、末尾不是 C 的观光路线数。

    当 n=2 时，长度为 2 、末尾是 C 的只有 AC 一条路线，末尾

不是 C 的有 AB,AD,AE 三条路线。所以有 X2=1 ，Y2=3 。

    一般来说，一条末尾不是 C 的长度为 n 的路线，加上一个 C ，可以

成为一条末尾是 C 的长度为 n+1 的路线。

    一条末尾是 C 的长度为 n 的路线，加上一个 A,B,D,E ，可以成为一条

末尾不是 C 的长度为 n+1 的路线。或者一条末尾不是 C 的长度为 n 的路线，

加上一个与本身末尾不同、与 C 也不同的字母，也可以成为一条末尾不是 C

的长度为 n+1 的路线。

   所以有递推关系式：

         Xn+1=Yn ，Yn+1=4Xn+3Yn ，n=2,3,4,… 。

   由上述递推关系式，逐步递推，可得：

   X3=Y2=3 ，Y3=4X2+3Y2=4×1+3×3=4+9=13 。

   X4=Y3=13 ，Y4=4X3+3Y3=4×3+3×13=12+39=51 。

   X5=Y4=51 。

   可见，长度为 5 、开头是 A 、末尾是 C 的观光路线共有 51 条。