长度为n的0、1、2字符串有多少个是含有两个连续的0,求递归关系这个字符串包含0,1,2,但不一定包含全

Question

长度为n的0、1、2字符串有多少个是含有两个连续的0,求递归关系
这个字符串包含0,1,2,但不一定包含全

Answer 1

换位思考,即去除掉不连续的
总共有3^n中情况
再考虑不连续的情况,又有以下几种(k表示0的个数)
k=0,2^n
k=1,n*2^(n-1)
k=2,C(n,1)*C(n-2,1)*2^(n-2)
k=3,C(n,1)*C(n-2,1)*C(n-6,1)*2^(n-3)
……
k=[n/2]