有哪些信誉好的足球投注网站- 1、本文档共13页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
《组合数学引论》
《组合数学引论》
－Chapter6
－
Chapter6
递推关系
递推关系
《组合数学引论》
《组合数学引论》
－Chapter6
－
Chapter6
§5.1递推关系的建立
§5.1递推关系的建立
递推关系几乎在所有的数学分支中都
有重要作用，它也是组合学中解决组合计
数问题的很好工具．如何建立递推关系，
已给的递推关系有何性质，求解递推关系
为递推关系的几个基本问题．
为一数列，第n项与其前面若干项联
系起来的关系式称为数列通项的递推关系.
一般来说,对于数列的递推关系,前面某些
个的值是已知的,称为初始条件,由这些已知
值通过递推关系可逐步求出.由递推
关系求出的一般表达式叫做解递推关系．
下面通过几个例子看看如何建立递推关系.
例1（Hanoi塔问题）有三根立柱A，B，C，在柱A上套
有n个大小不等的空心圆盘，这些圆盘从大到小构成圆塔形
．现在要把这n个圆盘搬移到B柱上，要求每次只能搬移一个
圆盘，且在搬移过程中大盘不能压在小盘上，问最少要搬移
多少次？
解：设满足题设条件的搬移次数为，
显然,下面建立的递推关系：
1.将A柱上面的n-1个圆盘搬到C柱上，
由假设搬移次数为．
2.将Ａ柱上剩下的最低下的一个圆盘搬
移到B柱上，搬移次数为1．
3.最后将C柱上n-1个圆盘搬移B柱上，搬移次数为.
由加法原理有递推关系：
由迭代法解得:
．
所以最少的搬移次数为
例2在信道上传输由a,b,c三个字母组成的长为n的字
符串,若字符串中有两个a连续出现,则信道就不能传输.令
f(n)表示信道可以传输长为n的字符串的个数,求f(n)满足
的递推关系.
解f(n)它可分为如下两类:
1.第1位是字母a,则第2位只能是字母b或c，所以这类字
符串有2f(n-2)个．
2.第1位不是字母a,则第1位只能是字母b或c，所以
这类字符串有2f(n-1)个．
由加法原理得的递推关系为
例3计算n位0,1字符串中“010”子串在第n位出现的字符串
有多少个?
解设“010”子串在第n位出现的长为n的字符串为f(n).
因为最后3位是“010”子串的n位字符串有2n-3个,其中“010”
子串在第n位出现的有f(n)个.而“010”子串不在第n位出现,当
且仅当最后5位为“01010”,并且“010”子串在第n-2位出现,所以
这类字符串共有f(n-2)个.
从而有
例4.一个圆形区域分成n个扇形区域，用k种颜色对n个扇
形着色，要求相邻扇形不同色，建立这样的着色方案数f(n)
满足的递推关系.
解用表示这n个扇形,着色方案数f(n)可分为两类:
(1)D与D同色，这时D有k-1种着色方案，由于D与D
1n-1n1n-2
异色，可将D与D看为相邻扇形区域，则扇形D至D有
1n-21n-2
f(n-2)种着色方案，所以此类着色方案为(k-1)f(n-2)种.
(2)D
文档评论（0）