请教大家这道题如何解

xiangyunl

由a b c 组成的n位字符串中不出现图像aa的字符串数目共有多少？

iminto

很好的一道题，该眼珠下下，哈哈

l0ivesuxing

很好的一道题目呀，有难度但很有意思，特容易实现解答

l0ivesuxing

很好的一道题目呀，有难度但很有意思，特容易实现解答

l0ivesuxing

很好的一道题目呀，有难度但很有意思，特容易实现解答

索路最高

楼主这道题是特定子串的研究范围，请去阅读<Combinatorial Enumeration> Goulden，里面的一节用两种生成函数与组合簇的方法，解决了所有的特定子串问题。
还有楼上给了递归公式是没错，但是要找解析解非常的麻烦。而且如果需要的图案和要求一多，比如要求出含有bababbc和abbcaba的所有长度为n的串，在这种两个图案都可以重复甚至可以以多种方式重复的情况下，离散的递归方法是不可行的。

muaqin

设n位字符有Sn种,则可以得到递推公式
* ]" v% E3 s/ y1 F9 D: d# t$ ESn=2*S(n-1)+2*S(n-2)
要排N个数,先排最高位,最高位如果是,b或c,则只要后面n-1位没有aa就行,也就是s(n-1),如果首位放a,则第二位只能放b,或c,余下的n-2位没有aa就行.所以递推公式为Sn=2*S(n-1)+2*S(n-2)
S(1)=3,S(2)=8,s(3)=22.....依次下去!

jtdu007

设n位字符有Sn种,则可以得到递推公式
Sn=3*S(n-1)+2S(n-3)
: J% F, A, H* _3 m1 R; sS1=3
S2=9
S3=22
3 B, B( N& h/ d* }$ n解特征方程即可.
: Z, A  p' n" X5 Y; r递推公式是这样来的:要排N个数,只需要先把前面N-1个数排好,后面再排一个数即可,但是当第N-1个数是A的时候,第N位不能是A,第N-1位是A,第N-2位一定不是A,所以只要前面N-3位按要求排好,第N-2位只能是B或C,有2S(n-3)种

DreaMathing

% w: g  T" {: [. {) o' I. S/ z我在想可以从a出现的次数上考虑，试图找到通项公式。
k=n时，a出现一次，一共有n×2*(n-1)种情况，
           a出现两次，一共有Cn2-(n-1) 种情况，
- O1 r( D$ J: s) j, }           a出现三次，一共有[(n-4)+(n-5)+...+1]+[(n-5)+(n-6)+...+1]+...+1再加上k=n-1时a出现三次的情况数，
+ [* c" V# \6 _1 ?6 P3 a% t* \+ h           a出现四次，一共有[(n-6)+(n-7)+...+1]+[(n-7)+(n-8)+...+1]+[(n-8)+(n-9)+...+1]+...+1再加上k=n-1时a出现四次的情况数，
. r4 f7 M* }; F5 @9 v           ......
n为偶数时，a最多出现n/2次，n为奇数时，a最多出现(n+1)/2次
再整理一下，递推式是出得来的吧，然后就好求了。

xuxiaolong

递推求解啊，。。。。