求满足约束条件的n厘米道路铺砖方式的递推关系及初始条件

云上老周

2026-5-19

嘿，我来帮你梳理清楚这个递推关系的推导过程！你已经定义了$a_n$、$b_n$、$c_n$这三个变量，这个思路非常好，接下来我们就基于这些定义一步步拆解：

我们可以把$b_n$拆成两种合法的子情况：

首个瓷砖是绿色（1cm）：因为绿瓷砖不能和蓝瓷砖相邻，所以剩下的$n-1$厘米道路的首个瓷砖不能是蓝色，这部分的铺法数正好是$b_{n-1}$（长度$n-1$且首个非蓝色的铺法数）。
首个瓷砖是红色（3cm）：红瓷砖和任何瓷砖都能相邻，所以剩下的$n-3$厘米道路可以是任意合法铺法，对应铺法数为$a_{n-3}$。

由此得到递推式：
$$b_n = b_{n-1} + a_{n-3}$$
（注：当$n<3$时，$a_{n-3}=0$，因为长度为负的道路没有铺法）

同样拆成两种子情况：

首个瓷砖是蓝色（2cm）：蓝瓷砖不能和绿瓷砖相邻，所以剩下的$n-2$厘米道路的首个瓷砖不能是绿色，这部分的铺法数对应$c_{n-2}$（长度$n-2$且首个非绿色的铺法数）。
首个瓷砖是红色（3cm）：和上面同理，剩下的$n-3$厘米道路可以是任意合法铺法，对应铺法数为$a_{n-3}$。

由此得到递推式：
$$c_n = c_{n-2} + a_{n-3}$$
（注：当$n<3$时，$a_{n-3}=0$；$n<2$时，$c_{n-2}$对应$c_0$，空铺法算1种）

总铺法可以拆分为三类合法情况：

由此得到递推式：
$$a_n = b_{n-1} + c_{n-2} + a_{n-3}$$

我们需要定义小长度道路的初始值，确保递推能正常启动：

$n=0$（空道路）：只有1种铺法（不铺任何瓷砖），所以$a_0=1$；$b_0=1$（空铺法属于首个非蓝色）；$c_0=1$（空铺法属于首个非绿色）。
$n=1$：只能用绿色瓷砖，所以$a_1=1$；$b_1=1$（首个是绿，非蓝色）；$c_1=0$（没有长度1的非绿色瓷砖）。
$n=2$：合法铺法为「蓝」「绿绿」，共2种，所以$a_2=2$；$b_2=1$（只有「绿绿」是首个非蓝色）；$c_2=1$（只有「蓝」是首个非绿色）。
$n=3$：合法铺法为「红」「绿绿绿」，共2种，所以$a_3=2$；$b_3=2$（「绿绿绿」「红」都是首个非蓝色）；$c_3=1$（只有「红」是首个非绿色）。

比如计算$a_4$：
用递推式可得：$a_4 = b_3 + c_2 + a_1 = 2 + 1 + 1 = 4$，和实际枚举的铺法（「绿绿绿绿」「绿+红」「蓝+蓝」「红+绿」）数量完全一致，验证正确。

如果想要消去$b_n$和$c_n$得到仅关于$a_n$的递推式，代入推导后可得：
对于$n \geq 5$，$$a_n = a_{n-2} + a_{n-3} + a_{n-4} + a_{n-5}$$
初始条件为$a_0=1, a_1=1, a_2=2, a_3=2, a_4=4$。

内容的提问来源于stack exchange，提问作者Noy