组合数学问题 5
将长度为n的、没有两个0或者两个1相连的三进制字符串(由0,1,2组成的字符串)的个数记为。首先建立的递推关系,然后求出的通项公式。...
将长度为n的、没有两个0或者两个1相连的三进制字符串(由0,1,2组成的字符串)的个数记为 。首先建立 的递推关系,然后求出 的通项公式。
展开
展开全部
将长度为n的开头为0的这样的个数记做a(n)
将长度为n的开头为1的这样的个数记做b(n)
将长度为n的开头为2的这样的个数记做c(n)
总数记做x(n)
则a(1)=b(1)=c(1)=1;x(1)=3,x(2)=7;
a(n)=b(n-1)+c(n-1)
b(n)=a(n-1)+c(n-1)
c(n)=a(n-1)+b(n-1)+c(n-1)=x(n-1)
三式相加x(n)=2x(n-1)+c(n-1)=2x(n-1)+x(n-2)
也就是x(n)=2x(n-1)+x(n-2),x(1)=3,x(2)=7
有了初始项和递推公式,通项公式就按照公式求就行啦,带根号和n次方的,不好打出来~
将长度为n的开头为1的这样的个数记做b(n)
将长度为n的开头为2的这样的个数记做c(n)
总数记做x(n)
则a(1)=b(1)=c(1)=1;x(1)=3,x(2)=7;
a(n)=b(n-1)+c(n-1)
b(n)=a(n-1)+c(n-1)
c(n)=a(n-1)+b(n-1)+c(n-1)=x(n-1)
三式相加x(n)=2x(n-1)+c(n-1)=2x(n-1)+x(n-2)
也就是x(n)=2x(n-1)+x(n-2),x(1)=3,x(2)=7
有了初始项和递推公式,通项公式就按照公式求就行啦,带根号和n次方的,不好打出来~
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询
广告 您可能关注的内容 |