求满足特定邻项差条件的{1,2,3,4}元素n元序列的计数递推关系

这个问题可以用状态转移的思路来推导递推关系，我一步步给你理清楚：

首先，我们定义四个状态变量，用来跟踪不同长度序列的末尾元素情况：

• $A_m$：长度为$m$，从1出发，最后一个元素是1的序列数量
• $B_m$：长度为$m$，从1出发，最后一个元素是2的序列数量
• $C_m$：长度为$m$，从1出发，最后一个元素是3的序列数量
• $D_m$：长度为$m$，从1出发，最后一个元素是4的序列数量（也就是你要找的$X_m$）

状态转移方程 #

根据题目中“相邻元素差的绝对值为1”的规则，每个状态只能从特定的前序状态转移过来：

• 末尾是1的序列，只能从末尾是2的序列走一步过来（因为1不能往左走，没有比1更小的元素）：$A_m = B_{m-1}$
• 末尾是2的序列，可以从末尾是1或3的序列走一步过来：$B_m = A_{m-1} + C_{m-1}$
• 末尾是3的序列，可以从末尾是2或4的序列走一步过来：$C_m = B_{m-1} + D_{m-1}$
• 末尾是4的序列，只能从末尾是3的序列走一步过来（因为4不能往右走）：$D_m = C_{m-1}$

初始条件 #

当序列长度为1时，只有开头的1，所以：
$A_1=1$，$B_1=0$，$C_1=0$，$D_1=0$

推导偶数长度的递推关系 #

你已经发现奇数长度的$X_n=0$，所以我们只需要关注偶数$n=2k$，令$f(k)=X_{2k}=D_{2k}$，现在推导$f(k)$的递推：

1. 由$D_m = C_{m-1}$，代入$C_{m-1}$的转移式，得到：
   $D_m = B_{m-2} + D_{m-2}$
2. 再把$B_{m-2}$用转移式展开：$B_{m-2}=A_{m-3}+C_{m-3}$，而$A_{m-3}=B_{m-4}$，$C_{m-3}=D_{m-2}$（因为$D_{m-2}=C_{m-3}$），所以：
   $B_{m-2}=B_{m-4} + D_{m-2}$
3. 又因为$D_{m-2}=B_{m-4}+D_{m-4}$，可以解出$B_{m-4}=D_{m-2}-D_{m-4}$，代入上一步的式子：
   $B_{m-2}=(D_{m-2}-D_{m-4}) + D_{m-2}=2D_{m-2}-D_{m-4}$
4. 最后把$B_{m-2}$代入$D_m$的式子：
   $D_m=(2D_{m-2}-D_{m-4}) + D_{m-2}=3D_{m-2}-D_{m-4}$

转换成$f(k)$的形式就是：
$$f(k) = 3f(k-1) - f(k-2)$$

验证递推式 #

用你给出的正确数值验证：

• 初始条件：$f(2)=X_4=1$，$f(3)=X_6=3$
• $f(4)=3*3 -1=8$，和你算的$X_8=8$一致
• $f(5)=3*8 -3=21$（这里你之前算的$X_{10}=18$是错误的，正确值应该是21）
• $f(6)=3*21 -8=55$（你算的$X_{12}=50$也不对，正确值是55）

总结 #

最终，对于偶数$n=2k$，符合条件的序列数$f(k)$满足递推关系：
$$f(k) = 3f(k-1) - f(k-2)$$
初始项为$f(2)=1$，$f(3)=3$。

备注：内容来源于stack exchange，提问作者user1260135