给定n，只有{1,2,3}字母表的长度n的字符串有多少

Question

...such，在字符串中的任何地方都不会有长度为3的子字符串，其中所有三个数字都存在？

换句话说，有多少字符串可以使以下任何一个字符串都不是子字符串："123“、"132”、"213“、"231”、"312“或"321”？

我偶然发现了这样的一个问题，并试图找出复发，但我的重复是不正确的(我比较它的代码与蛮力程序)。

我现在要说的是：

f(n) = 3f(n - 1) - 6f(n - 3)

我们知道，我们有f(n) =3f(n-1)给出的所有可能的字符串，我们也知道有6种方法我们不想考虑：

123 concatenated with all the ways to make f(n-3)
132 concatenated with all the ways to make f(n-3)
213 concatenated with all the ways to make f(n-3)
231 concatenated with all the ways to make f(n-3)
312 concatenated with all the ways to make f(n-3)
321 concatenated with all the ways to make f(n-3)

有什么我缺少的洞察力吗？这在我脑子里是有道理的，但这不对。

Answer 1

容易解释的方法：

让我们

F(n) = P(n, 2) + P(n, 1)

其中P(n，2)是字符串数，以两位数(如xxx13)结尾，

P(n，1)是字符串数，以两等号(如xxx22)结尾。

然后

P(n, 2) = P(n - 1, 2) + 2 * P(n-1, 1)  
//we can add only a to the end of xxxab, and both b and c to xxxaa

P(n, 1) = P(n - 1, 2) + P(n - 1, 1)   
//we can add only b to xxxab, and only a to xxxaa
//note it is equal to F(n-1)

F(n) = 2 * P(n - 1, 2) + 3 * P(n - 1, 1) = 
       2 * (P(n - 1, 2) + P(n - 1, 1)) + P(n - 1, 1) =
       2 * F(n - 1) + P(n - 1, 1) =
       2 * F(n - 1) + F(n - 2)

初值

F(1) = 3
P(2, 2) = 6
P(2, 1) = 3
F(2) = 9

例如：

F(3) = 21 (9 * 2 + 3) (quick check: 3^3 - 3! = 27 - 6 = 21)
F(4) = 51
F(5) = 123
F(6) = 297
F(7) = 717

所以：

 F(n) = 2 * F(n - 1)  +  F(n - 2)