请教大家这道题如何解

xiangyunl

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

liujiandong

要分类吧，应该分类 然后求和 我想是这样的 最终是个数列题

liujiandong

我看是不是可以化归为考虑n组三元数组的问题了

xuxiaolong

递推求解啊，。。。。

DreaMathing

$ a$ N$ M' ~/ Y. i: b; i4 c: G+ X: o
2 H' z1 T! ^8 v% i! l' ?# M' r+ f我在想可以从a出现的次数上考虑，试图找到通项公式。
k=n时，a出现一次，一共有n×2*(n-1)种情况，
3 ^0 T5 w, g8 d, |6 Z           a出现两次，一共有Cn2-(n-1) 种情况，
, j( x9 i7 }4 c. Z9 \           a出现三次，一共有[(n-4)+(n-5)+...+1]+[(n-5)+(n-6)+...+1]+...+1再加上k=n-1时a出现三次的情况数，
           a出现四次，一共有[(n-6)+(n-7)+...+1]+[(n-7)+(n-8)+...+1]+[(n-8)+(n-9)+...+1]+...+1再加上k=n-1时a出现四次的情况数，
- l* t7 q* f/ ?- r% u$ n4 X7 ^           ......
$ |9 x# [! d  e6 y' v, v+ g2 t3 mn为偶数时，a最多出现n/2次，n为奇数时，a最多出现(n+1)/2次
再整理一下，递推式是出得来的吧，然后就好求了。

jtdu007

设n位字符有Sn种,则可以得到递推公式
Sn=3*S(n-1)+2S(n-3)
S1=3
S2=9
S3=22
解特征方程即可.
递推公式是这样来的:要排N个数,只需要先把前面N-1个数排好,后面再排一个数即可,但是当第N-1个数是A的时候,第N位不能是A,第N-1位是A,第N-2位一定不是A,所以只要前面N-3位按要求排好,第N-2位只能是B或C,有2S(n-3)种

muaqin

设n位字符有Sn种,则可以得到递推公式
Sn=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.....依次下去!

索路最高

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

l0ivesuxing

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

l0ivesuxing

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