满足特定条件的字符串计数：计算a₄与a₂₀₁₅

首先，我们先明确问题的核心约束：字符串必须是前半部分全为偶数（2、4），后半部分全为奇数（1、3）（所有偶数在奇数之前），且数字1恰好出现一次。基于这个结构，我们可以从两种思路入手：直接推导通项公式，或者构造递推关系。

一、直接推导通项公式 #

我们可以按「奇数部分的长度」拆分计算：设奇数部分长度为m（m≥1，因为必须包含1），则偶数部分长度为n-m：

• 偶数部分：每个位置有2种选择（2或4），共2^(n-m)种可能；
• 奇数部分：长度m中恰好有1个1，其余为3，共有m种选择（选1个位置放1）。

因此，总数量是对所有可能的m求和：

aₙ = Σ（m=1到n）[2^(n-m) * m]

我们可以用求和公式化简这个式子：
令k = n-m，则m = n-k，当m从1到n时，k从n-1到0，代入得：

aₙ = Σ（k=0到n-1）[2^k * (n - k)]

利用已知的求和公式：

• Σ（k=0到n-1）2^k = 2ⁿ - 1
• Σ（k=0到n-1）k*2^k = (n-2)2ⁿ + 2

代入后化简可得：

aₙ = 2^(n+1) - n - 2

验证小例子 #

你提到的n=3时，代入公式得2^4 -3 -2=16-5=11，和你的结果一致，说明公式正确。

计算a₄和a₂₀₁₅ #

• a₄ = 2^(5) -4 -2 = 32-6=26
• a₂₀₁₅ = 2^(2016) -2015 -2 = 2²⁰¹⁶ -2017

二、构造递推关系 #

如果你想用递推的方式求解，可以定义三个状态来拆分问题：

• xₙ：长度为n的全偶数字符串（无奇数，1出现0次）
• yₙ：长度为n的字符串，前半部分偶数、后半部分全为3（有奇数但1出现0次）
• aₙ：长度为n的满足条件的字符串（偶数在奇数前，1恰好出现1次）

状态转移：

1. xₙ的递推：每个全偶数字符串可以在末尾加2或4得到更长的全偶数字符串，因此xₙ = 2*xₙ₋₁，初始x₁=2（"2"、"4"），解得xₙ=2ⁿ。
2. yₙ的递推：长度n的yₙ可以由长度n-1的yₙ₋₁末尾加3，或长度n-1的xₙ₋₁末尾加3得到，因此yₙ = yₙ₋₁ + xₙ₋₁，初始y₁=1（"3"），解得yₙ=2ⁿ -1。
3. aₙ的递推：长度n的aₙ有三种来源：
   • 长度n-1的aₙ₋₁末尾加3（不能加偶数或1）
   • 长度n-1的yₙ₋₁末尾加1（此时1恰好出现1次，且偶数都在奇数前）
   • 长度n-1的xₙ₋₁末尾加1（前半全偶数，加1后满足条件）
     因此递推式为：aₙ = aₙ₋₁ + yₙ₋₁ + xₙ₋₁，代入yₙ₋₁和xₙ₋₁的表达式得：

   aₙ = aₙ₋₁ + 2ⁿ -1
   

   初始条件a₁=1（只有"1"满足），解这个递推式最终也会得到和之前一致的通项公式aₙ=2^(n+1)-n-2。

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