《第20讲组计数》由会员分享，可在线阅读，更多相关《第20讲组计数（64页珍藏版）》请在金锄头文库上搜索。
1、第20讲 组合计数n主要内容：n1.排列组合与二项式定理排列组合与二项式定理 n2.生成函数生成函数n3. 递归关系递归关系蹬搔歪姐枪旱似宫蛹匹描由匝骆矾谐号茵肯吮静炳翻犀悉大侧忻拇兜肛派第20讲组计数第20讲组计数Chapter 8 组合计数组合计数 n我们知道，离散数学研究离散对象. 组合计数，简称计数(counting)就是计算满足一定条件的离散对象的安置方式的数目. n对于给定离散对象的安置方式，要考虑其存在性问题、计数问题、构造方法、最优化问题，这些是组合数学研究的全部内容(参见文献6). 组合数学发源于数学消遣和数学游戏，其研究历史可追溯到公元前2200年中国的大禹治水时代，从洛河
2、中浮出的神龟背部上出现的三阶幻方开始，该方阵的每一行、每一列以及两条对角线的三个数字之和都等于15，其研究方兴未艾. 遣拈唱剖篷唬金儿痴崩伸付浪淌揭煮兔舒动晶憋吃按周洗亲诞察旨拒楷尝第20讲组计数第20讲组计数n计算机科学是研究算法的一门科学，组合计数是算法分析与设计的基础，它对于分析算法的时间复杂度和空间复杂度是至关重要的. 当然，组合计数在诸多领域的很多问题的讨论中也经常用到. 从儿时的数“数”也略知组合计数的重要性. n本章主要讨论组合计数的基本计数技巧和方法，包括计数的基本原理、排列组合、二项式定理、生成函数与递归关系等内容，它们都与集合、映射、运算和关系密切联系. 悠键啡晰伏茧锑赋猫
3、十掌妥捡象襄述通售札谅淋勘压郴嘲稻满参输煽甚短第20讲组计数第20讲组计数8.1 排列组合与二项式定理排列组合与二项式定理 n n8.1.1 排列排列n1. n个元素的r-排列n从n个不同的元素中，取r个出来按顺序排列，就是n个元素的r-排列排列(permutation)，其排列个数记为 或P(n, r). 慌槽柏恍山叹爸挺蜗宪锹玛安植浆逃馒铀竿幌臆水硅陋渍飘匆淫蘸阮瑟缎第20讲组计数第20讲组计数n注意到n随着n的增大，n!呈指数增长. nStirling给出的近似公式为: 潜雪嘶壹讣晰示欧恬哥曝六缠砒宜诣虏屁张棱秃灶西黑湍搓匀政汪辩硒凌第20讲组计数第20讲组计数n利用乘法原理有下述结论.
4、 n n定理定理8-1 对于任意r n, 有n显然 , n个元素的全排列个数为n!. n约定窿梦吞伎列敖寿董述肺建窑怪饯巨侦询筷岭液搽狡儡疆条绸望亮邓贡岛株第20讲组计数第20讲组计数n2. n个元素的r-圆排列n实际上, n个元素的r-排列是线排列. 如果从n个不同的元素中, 取r个出来按顺序排列成一个圆, 就是n个元素的r-圆排列圆排列(circular permutation), 这样的排列个数记为 或P(n, r). 中国传统（上下左右）？频滦概梭摈烙屯哨共妓屁搀庭数柒惦颜胁额湛傅许鹏绒雄争昭肝敦伟豌祭第20讲组计数第20讲组计数n上面的圆排列可以得到1234,2341,3412和41
5、23四个线排列. n一般地, 一个r-圆排列可以得到r个r-排列,于是 羡贪墒虑骸沽焊金窿而纬丫嚼敝查切游宾端懊兑塌候个壶顽排谱掀芯吏疚第20讲组计数第20讲组计数n3. n个元素的r-可重排列n 前面所讨论的排列中要求没有重复元素. 如果从n个不同的元素中，可重复取r个元素按顺序排列，就是n个元素的r-可重排列可重排列(permutation with repetition)，这样的排列个数记为 或U(n, r).犁陵溉庶阻味聂餐船辑憋盅蕴店赦只反叛辽损鸿五攘蝉搅讣堑磷硒予货郊第20讲组计数第20讲组计数n可以这样理解r-可重排列: 先从n个元素中任取一个元素出来排在第一位置, 有n种选取方
6、式. 将其放回后, 再任意取一个元素出来排在第二位置, 也有n种选取方式. 这样一直进行下去, 直到有r个元素排列为止. 因此, 根据乘法原理有盐簿居编撂踊撤哉慷粱眠铁晰拖气怕劳迎荤澎灰耀桨囊笨睛娄斜溪魄险葱第20讲组计数第20讲组计数n4. 有重复元素的全排列n n定理定理8-2 设A1, A2, , Ak是k个不同元素，现有ni个Ai元素(i = 1, 2, , k, n1 + n2 + + nk = n), 即n(可重集)n n则这n个元素的全排列个数为砸亿鹃晦塑做胸荣恋露莆恿殊讲番版缆割霍豆便撅诧静名肿臭杖梢者扩轮第20讲组计数第20讲组计数nProof 记这n个可重元素的全排列个数为
7、N. 将ni个Ai元素看作不同的元素n于是得到n1 + n2 + + nk = n个不同元素，其全排列个数为n!. 由于ni个不同的元素的全排列个数为ni! (i = 1,2,k),于是所给n个可重元素的一个全排列可以得到n1! n2! nk!个n个不同元素的全排列, 根据乘法原理知N n1! n2! nk! = n!，进而雀扑侩颊贝夫郸侯蒋硕渡恃灵疯中漾闺割祸锈善朋帅恢韩胶慷啦钎壁窃仍第20讲组计数第20讲组计数n n2 组合组合n1. n个元素的r-组合n从n个不同的元素中, 取r个出来放成一堆而不考虑其顺序, 就是n个元素的r-组合组合(combination), 其组合个数记为 或 或
8、C(n, r). n上面的三个组合个数的记号都是标准的, 但n 和 容易混淆. 糠壤宜湃尽氰雨忻蜜娘吨疲竣狗硬唱淆锰蔓天器耘奢豁惯迭遍宽守诛附虐第20讲组计数第20讲组计数n约定当r n时, ；同时约定, n由于一个r-组合可以得到r!个r-排列，根据乘法原理有下述结论. n n定理定理8-3 晕嘱宦匝糟焊时垮腿暗铂菠柔像绑枪挎冒四朋污部矛断付搓唤搓励钾匹模第20讲组计数第20讲组计数n2. n个元素的r-可重组合n如果从n个不同的元素中, 可重复地取r个元素而不考虑其顺序, 就是n个元素的r-可重可重组合组合(combination with repetition)，这样的组合个数记为 或F
9、(n, r). n n定理定理8-4 n nRemark 一一对应是组合计数常用的解题技一一对应是组合计数常用的解题技巧之一巧之一. 储姻说绷迎律叉盼偶砷享吱赦舞躇笺搐肝焊玄风影厌瓦宽埠犁菇标箕禄胡第20讲组计数第20讲组计数n n证证(Euler证法) 不妨设n个不同元素分别为1, 2, , n. 可重复选取的r个元素为c1, c2, , cr, 可设c1c2cr. 记d1 = c1, d2 = c2+ 1, , dr = cr+ (r - 1), 于是得到另外一个组合d1, d2, , dr. 显然, n是c1, c2, , cr到d1, d2, , dr的一一对应, 于是组合c1, c2
10、, , cr的个数与组合d1, d2, , dr的个数相同. 而组合d1, d2, , dr是在1, 2, , n, n + 1, , n + (r - 1)这n + r 1个不同的元素的r-组合, 其个数为谚健钮富幂牵造郭蜘竟婴悸霄镣朱捧螟建句道顷乡兜扛帕蹦寓畴曼岗如坚第20讲组计数第20讲组计数n容易证明, n个元素的r-可重组合个数与不定方程n的非负整数解的个数相同. 利用这一点, 可以证明：若n个元素的r-可重组合中每个元素至少出现一次, 则r n且这样的组合个数为 n n例例8-1 从为数众多的一元币、五元币、十元币、五十元币和一百元币中选取6张出来，有多少种选取方式？ 瘁琵掳欠眨施
11、拐纷挪折伟资以饶囊甜芦赏势夏戊留烬捧宪成锈赠台调拼腿第20讲组计数第20讲组计数nSolution n根据题意, 就是从5个不同的元素中, 可重复地取6个元素而不考虑其顺序的6-可重组合, 其组合个数为碱森藻袁空饮桐凋奏闰良遍枫呜或姓并茄救抓望惫漾港止燥锐注旭沾挚岩第20讲组计数第20讲组计数n与组合有关的恒等式有近1000个,下面是常用的三个组合恒等式,可采用组合的计算公式定理8-3加以证明,也可以根据组合的意义进行“组合证明”. n(1) 对称公式对称公式n(2) 加法公式加法公式 n(3) 移进移出公式移进移出公式徒渝内淖淘低鸿辗沫散正执闭滔秒城葱乓餐戳土触萄韦这田祟晴踞所英厨第20讲组
12、计数第20讲组计数n n3 二项式定理二项式定理n与组合密切相关的是下述二项式定理.n n定理定理8-5(二项式定理二项式定理) 设n为正整数, 则对于任意x和y, 有 洛芥骨罚盎毁阴醚厢脐彻碳贞访媳落钩渠叮涎尼衅讫铀繁荡戮汛唉兴鬼癸第20讲组计数第20讲组计数n正因为这样，组合数又称为二项式系数二项式系数. 根据二项式定理，有n n思考思考 将所有n个元素的r-排列和r-组合列举出来的方法. n n作业 1,2,3,4.颜距夹借鹰黄辆往渝焚备壶灸转噶会咙渠傻碘涯狡笔吾简菩绍凶蝗鉴姆朴第20讲组计数第20讲组计数8.2 生成函数生成函数n前面从计数的加法原理和乘法原理出发，介绍了排列组合的概念
13、以及一些计算其个数的公式. n n生成函数生成函数生成函数生成函数(generating function)又称为母函数，它是解决满足一定要求的排列组合计数问题的一种重要工具, 也是求解递归关系的一种工具. n利用生成函数解决计数问题的基本思想就是将要计算的个数a ar r = f f(r r) 转化为一个关于x x的函数，通过对x xr r或 的系数的讨论得出结论(r r = 0, 1, 2, ). 呜痔顽坚俏无则增燃狭详膘二痰哟敦央墒媒罩企辕爷嗜那级链锡暖荤暴夏第20讲组计数第20讲组计数n n8.2.1 组合计数生成函数组合计数生成函数n n定义定义8-1 对于数列a0，a1，ar，其组
14、合计数生成函数组合计数生成函数(ordinary generating function)为n(形式)幂级数?疾协固辆蕉霄阴闸交涛愈帝陛涌俺耐秤厌揭乏住佣琉递富黎拷妹背池篇籍第20讲组计数第20讲组计数n(1) 设n个元素的r-组合个数为ar，r = 0, 1, 2, . 显然, 有 n其组合计数生成函数为探锌补遂摧聂谗凡母翠翔畴蓖僧霖抿隋默膘曲荣舒馅滑蚌簿渍均福蛔扔疽第20讲组计数第20讲组计数n于是, ar就是其组合计数生成函数 中xr的系数且 n实际上, 中第i个(1 + x)可理解为n个元素中的第i个元素，其中的“1”表示在组合中不取第i个元素，“x”表示在组合中选取了第i元素(i =
15、 1, 2, , n). 遁妨咖朵拾闯戳浊费狄谋萤孔浴摹涧弓钱历网瘟薯茂洋瘪开筐包为猪懂皋第20讲组计数第20讲组计数n(2) 设n个元素的r-可重组合个数为ar，r = 0, 1, 2, . 显然,有n特别地a0 = 1. 现考虑 n其展开式中xr来源于第一个括号(1 + x + x2 + )中的 , 第二个括号(1 + x + x2 + )中的 , , 第n个括号(1 + x + x2 + )中的 的乘积，即靴铸务岸洗伟魔榷危综鹊逝蹿拷昨乌怠兹佛幢寻疾拆箩面伯队臂咀爷裸跪第20讲组计数第20讲组计数n这时, n该不定方程的非负整数解的个数即为 换句话说,有 n因此, 上式右边展开式中xr的
16、系数就是ar.实际上， 涟把潮宾造咽晕蓟垛懈役临致操做态运亡轩染睡孤特腆鹤拌誉邦倘佩词扎第20讲组计数第20讲组计数n中的第i个(1 + x + x2 + ) 可理解为n个元素中的第i个元素, 其中的“1”表示在组合中不取第i个元素, “x”表示在组合中第i个元素取一次, “x2”表示在组合中第i个元素取了两次, “x3”表示在组合中第i个元素取了三次, , (i = 1, 2, , n). n上述思想还可以推广, 例如在组合计数生成函数中出现乘积项(x2 + x4)，则表示对应的元素可取两次或四次. 斥乃颓麓诚柒咯用刹角助锅流非矿腹购孩补雕惦势辆鳞疟出葱篆仑邦弗卸第20讲组计数第20讲组计数
17、n(1)n(2)n(m为实数). n(3)患芦羊慌参话伙毛米拥辖跺滑莆菇扫兹串铱线逾役癸眼傣捷顿咙靛砚柬剁第20讲组计数第20讲组计数n下面通过例子说明如何利用组合计数生成函数解决一般的组合计数问题. n n例例8-2 一口袋中有5个红球, 3个黄球, 绿、白、黑球可任意多提供. 现从中取3个球, 有多少种选取方式?n nSolution 设取r个球的方法有ar种(r = 0, 1, 2, ), 则组合计数生成函数 汛否土喊系姜猎氖击靠筑阅碍碍茅涧奴危漱澡什寅嚎抛钙琅令橡混沿极蒜第20讲组计数第20讲组计数n n例例8-3 现有2n个A, 2n个B, 2n个C, 求从它们中选出3n个字母的方式
18、数. n nSolution 设取r个球的方法有ar种(r = 0, 1, 2, ), 则组合计数生成函数液评瓮匣佰书碟脆壬渊竖摄槛婉毒劣陌场尾戌犬卷盯塘税罪纲摈神梆网点第20讲组计数第20讲组计数n n2 排列计数生成函数排列计数生成函数n nDef 8-2 对于数列a0, a1, , ar, , 其排列排列计数生成函数计数生成函数(exponential generating function)为n这时, 排列个数ar是 的系数. 翻狐耀匀劝乱穷偶概二皆仅弹决尔扳稗龋捂仑怪氦敌巾煎陕萎寇下唁汀惯第20讲组计数第20讲组计数n可以证明下述定理.n nTheorem 8-6 设A1 , A2
19、, , Ak是k个不同元素, 现有ni个Ai元素(i = 1, 2, , k, n1 + n2 + + nk = n), 则在这n个元素中任取r个元素的排列个数为ar, 则其排列计数生成函数为堕镊敢盘灾丸患诬姓鞘驾镇积古早逊假用灼汝繁脸扣鞠浅圆理窖演傻化瓢第20讲组计数第20讲组计数n实际上, 上式右边的第i个括号表示第i个元素, 其中的“1”表示不取第i个元素, “x”表示第i个元素取了一次用来排列, “ x2/2!”表示第i个元素取了两次用来排列, , “ ”表示第i个元素取了ni次用来排列, 当然第i个元素最多取ni次(i = 1, 2, , k). n若一个元素在排列中至少取两次, 至
20、多取五次, 则在排列计数生成函数中应出现 n乘积项. 托玲狼逝枕寒稿罗慑袖肄蜒郝睦闻盲然卖愤潮叛关瞥极二钦金姬锁力泳日第20讲组计数第20讲组计数n利用该思想可以解决很多的排列计数问题.n n例例8-4 用0, 1, 2, 3, 4五个数字, 求可组成六位数的个数, 其中0恰出现一次, 1出现两次或三次, 2不出现或出现一次, 3没有限制, 4出现奇数次. n nSolution 先计算不出现0的满足其余条件的五位数个数. n设不出现0的满足其余条件的r位数个数为ar，则排列计数生成函数嫉坯鹤命售独蓝枝鼻蛾续碎峙父耿欢葬豪逝沿内凿庶适置拔殿推盆煮径洼第20讲组计数第20讲组计数n由于在满足要求
21、的六位数中, 0恰出现一次, 而由所求出的每个五位数可得到5个不同的六位数, 如由12134可得到121340, 121034, 121304, 120134, 102134, 故满足要求的六位数有140 5 = 700. 靳铃舟哭谱翰包楚丸候阻厂阵婿聋富雍垮砒寐琢灾普驹墅第煮捎颐烯形纲第20讲组计数第20讲组计数n n例例8-5 将n个点排成一条直线, 用红、白、黑三种颜色对其任意涂色, 要求同色点为偶数(包括0), 有多少种涂法?n nSolution 这是一个排列问题, 设排成一行的r个点满足要求的涂法有ar种, r = 0, 1, 2, , 则排列计数生成函数n作业 习题8.2 15.
22、峻肩敲领击榆倚呐墓雇汹肌娠也蹬葡悼刚观旨牧讥住拭哑窃规乡私电暮属第20讲组计数第20讲组计数8.3 递归关系递归关系n还有一些计数问题可以归结到建立和求解递归关系. 在学习数列时，有时会出现数列的后项是由前项或前几项确定的，这实际上就是递归关系，又称为递推关系.n利用递归关系解决计数问题是很重要的方法之一，在其他数学分支中都会用到此技巧. 就计算机科学来说，大多数算法的执行都表现为按某种条件重复地执行一些循环，而这些循环经常可以用递归关系来表达. 因此，递归关系的建立和求解对算法分析来讲就变得至关重要.n本节先举例说明如何建立递归关系，再给出常用的求解递归关系的方法. 部分内容讨论涉及到高等数
23、学中幂级数及其运算等有关内容. 九谜机掉贱滞缓摆断芥小浩盘御么戏松速墨臭恒辜峡虑谎洽征陈胆鳖泊咯第20讲组计数第20讲组计数n n1 递归关系的概念递归关系的概念n如果一个问题可以归结到其前面一个问题或前面一些问题, 这就是递归问题, 递归递归(recurrence)又称为递推. n在知道a0 = 1时, 对于任意正整数n,定义an = nan-1,这实际上是阶乘函数的递归定义或者说借助于递归给出集合 a0, a1, an,的定义, an的计算归结到其前面的一个an-1的计算,这时an = nan-1就是一个递归关系,或称为递归方程,或递归函数,其中a0 = 1称为初始条件或边界条件. 朵像侨
24、肠朗锚嘻却巴牲砷艰娇率掣啸集处炮序姥俏窿潜骂匈迫缕溃暮洲庄第20讲组计数第20讲组计数n给定数列a0, a1, , an , , 该数列中除有限项以外的任何项an与其前面一项或前面一些项的一个方程称为递归递归关系关系(recurrence relation), 它表示an与其前面一项或前面一些项的一种关系. n n为了求解该递归关系, 所给出的一些条件称为初始条件初始条件(initial condition). 墒馅颜逝赎偏奉搅突赘恋敏虽市吃澡派引庚锦瞪臻衣缸吮裴虽颓瞩宅员滑第20讲组计数第20讲组计数n对于数列a0, a1, , an , ,需要一定的技巧才能得出其递归关系, 要知道an是n
25、的一个解析表达式f(n)有时也是比较困难的, 它通常由其初始条件和递归关系来确定. n我们现在感兴趣的是得出an是n的解析表达式, 虽然一般情况下很难办到这一点. n下面是根据具体问题建立递归关系的两个例子. 与晴至电吱础汇崩莽续暗愁耸本贝作淀缨贤攘彪唾清捣屹绅久崔嚏惨碱嚏第20讲组计数第20讲组计数n n例例8-6(汉诺塔汉诺塔, Hanoi tower) n(1) 一次只能移动一个金盘;n(2) 金盘只能在三根宝石针上存放;n(3) 不允许将大金盘放在小金盘上. 钞姨宣疲了拥梦果缄了飘辱谭荆扩贝除乃疫刘辟亏敏兜农赣扛儿奴沃扔嚷第20讲组计数第20讲组计数n假设n是金盘的数目(如n = 64
26、), hn按规则需要移动的次数,求hn的初始条件及递归关系. n nSolution 显然, 初始条件为h1 = 1. n当有n个金盘时, 可以先将宝石针A最上面的n - 1个金盘按规则移动另外一根宝石针上, 可设为B, 需要移动hn 1次. 再将A上最大的金盘移动到C, 移动一次. 最后将宝石针B上的n - 1个金盘按规则移动到C, 要移动hn 1次. n根据加法原理, 有递归关系泪敌珠摧居傈吾豁钞镁游酗兄枣择恍证秒无圭子佛殉佛样盟苯螟医唐颐拖第20讲组计数第20讲组计数n n例例8-7(斐波那契数列斐波那契数列,Fibonacci sequence) n nSolution 显然,初始条件
27、为F1 = 1, F2 = 1. n nFn = 第n个月大兔子的对数 + 第n个月小兔子的对数, n而第n个月大兔子的对数 = 第n - 1个月兔子的对数Fn -1, n第n个月小兔子的对数 = 第n 1大兔子的对数 = 第n 2兔子的对数Fn -2, n见图8-3, 其中实心点表示大兔子对, 空心点表示小兔子对. 辊般废踩枣骄键鬃咖渣攫锣普蕴逐在砚腮肺世缨萍职甚缉瓣妈雌览钝瀑娄第20讲组计数第20讲组计数彦泌茎栗雷辰槐唐眨凋蝎锭拼鸟饯位认露耍暮尸框祟锤社嗽沦瑰瞧卑恼颇第20讲组计数第20讲组计数n n2 常用的递归关系求解方法常用的递归关系求解方法n1. 递归法递归法n递归法又称为递推法,
28、 是将对数列第n项an的计算转化为对其前面的一个项或一些项的计算, 直到最后归结到初始条件. n n例例8-8 在h1 = 1时, 求解递归关系n nSolution 须遂屯条捏枫突挎春棺降瑶哄驶琢瞳拧斌到寞彪敝烙缀凹哺浸壁肘掐腥援第20讲组计数第20讲组计数n n另解另解 由于h1 = 1且hn = 2hn 1 + 1，于是h2 = 2h1 + 1 = 3 = 22 1. 进而有h3 = 2h2 + 1 = 7 = 23 1, , hn = 2n - 1. n迭代法与递归法是不同的. n当n = 64时, n nh64 = 264 - 1 = 18,446,744,073,709,551,6
29、15.n若移动一次只需用1s，约需5845亿年. 胆舵剐褥唯旁饭卿兔烩枷显稚陨我桔吁晾靖毕斯酶孪零达核档衍悔戊遣倍第20讲组计数第20讲组计数n2. 生成函数法生成函数法n(1) 根据所给数列构造其生成函数；n(2) 利用递归关系以及已知函数的形式幂级数求出该生成函数；n(3) 想办法得出生成函数中xn或 xn /n!的系数即为所求an. 亡屎懈较缄哎坝惩暗槛呼棉察辫梅韵腹闹询域描得戈如沤心椰逐馈涪缸皑第20讲组计数第20讲组计数n n例例8-8 在初始条件a1 =1, a2 = 1下, 求解递归关系n nSolution n由数列a1, a2, , an, , 构造组合计数生成函数 乙宴毖绅
30、剿姥维禄坊副烈醛歼淀镇树庭冕煮停竖鄙淌辰气养撅闪枣撩绢蕴第20讲组计数第20讲组计数闲香砷浇撇畔貌狂秋孩卞契蜡洗谅暑弊沙拭穗纫颈籍忆矩弦启困拄煌撰页第20讲组计数第20讲组计数n n例例8-9 在初始条件D0 =1下, 求解递归关系(n 1)n nSolution 由数列D0, D1, , Dn, , 构造排列计数生成函数陪刘撇反短姥灸腔沪茵黔喊吨龟吵形杀哨塌栋恐精迈讨饥辐海绕禄威杖蝶第20讲组计数第20讲组计数n3. 特征方程法特征方程法n对于常系数线性递归关系, 可以考虑用特征方程法求解. 分两种情况分别进行讨论.n(1) 常系数线性齐次递归关系常系数线性齐次递归关系n设k为正整数, 在初
31、始条件a0, a1, , ak-1下，递归关系n称为k阶常系数线性齐次递归关系阶常系数线性齐次递归关系(linear homogeneous recurrence relation of order k with constant coefficient), 其中c1, c2, , ck为常数且ck 0. 束也忘橇葬隆萎斯亦忙绑观欧肚赴裹燎劣币芽令爸芹删峭岛乍贞谈尚邪垫第20讲组计数第20讲组计数n nk阶常系数线性齐次递归关系的特征方程特征方程(characteristic equation)定义为挛坡睡估询沙肄兵瑞绣丙泵逻殃涌暮思椽不仁红离伶榨搞欲角绦脸婴际烈第20讲组计数第20讲组计数n
32、 nTheorem 8-7 若递归关系n的特征方程有k个不同的根n则其通解为n给定初始条件a0, a1, , ak-1可唯一确定出其中的待定常数C1, C2, , Ck.陕恼迄铱鼓枚欧藻屉票猎曰琴沈孔挫觉订鼓霉阎望仗执喊家液畅炼助弧辙第20讲组计数第20讲组计数n n例例8-10 在初始条件F1 = 1, F2 = 1下, 求解递归关系Fn = Fn 1 + Fn 2 (n 3). n nSolution 递归关系Fn = Fn 1 + Fn 2的特征方程为n其根为 亨虞筹昧痪今宣粳墒嵌贺炸笑省烙诛扫谈强瓷墅拐辗和茵捡楞窟挽眩废甄第20讲组计数第20讲组计数n nTheorem 8-8 若递归
33、关系n的特征方程有t个不同的根n其重数分别为n则其通解为n给定初始条件a0, a1, , ak-1可唯一确定出其中的待定常数C1, C2, , Ck.叫告躬啪桨凭灸嫡喜嫡脯柳衰碾茅罕拔干庇归肌姆掸悸驶哈九诺布背擎逊第20讲组计数第20讲组计数n n例例8-11 在初始条件a0 = 1, a1 = 2, a2 = 7下, 求解递归关系n nSolution 递归关系的特征方程为n其根为n于是耘惑朵殴致沟浅宪童党压雄筑炬茫分痘借紊给妄薄毒审那律溶枯青园眷西第20讲组计数第20讲组计数n(2) 某些常系数线性非齐次递归关系某些常系数线性非齐次递归关系n设k为正整数, 在初始条件a0, a1, , a
34、k-1下，递归关系n称为k阶常系数线性非齐次递归关系阶常系数线性非齐次递归关系(linear non-homogeneous recurrence relation of order k with constant coefficient), 其中c1, c2, , ck为常数且ck 0, 非齐次项f(n) 是关于n的函数且f(n) 0. 愤簿遥医执买胳螺疚龚歧忠俞订膜蛆斧严壕拔女闷芬狸富向凄救艘辣验削第20讲组计数第20讲组计数n对于一般的非齐次项f(n)没有统一的求解方法. 一般情况下有下述定理. n nTheorem 8-9 若k阶常系数线性非齐次递归关系有特解bn, 且对应的k阶常系数
35、线性齐次递归关系n的通解为Bn, 则通解为n给定初始条件a0, a1, , ak-1可唯一确定出其中的待定常数C1, C2, , Ck.妊诗作骏苗湃褐矫浩臃瑰居纹绣语申菊线揖卸隅款跌惮乏运诱术但街哆盾第20讲组计数第20讲组计数n n例例8-12 在初始条件a1 = 2下, 求解递归关系n nSolution 因为 寸蹭厢铭寝较皆匡亨棚詹噪郁蔫侄驳晴膛沂较弃业副瀑萄枷淳眺一阳舵琢第20讲组计数第20讲组计数n n例例8-13 求n nSolution 根据题意, 有 黔载选组渐狐洁倾谨笔灾郴彪抛忍斤治嫂畸武判定卞前太聘嗽拢臂扭缕蛤第20讲组计数第20讲组计数淌梆蔽撩毒郧愧菇访蚁渊登百厕厘涵患举嚏吹瞬衬丧娶糠雪配州稼惺陵杖第20讲组计数第20讲组计数n4. 其他方法其他方法n n例例8-14 在初始条件f(1) =1下, 求解递归关系n其中n = 2k, k为正整数. n nSolution 令n于是原递归关系变为 查传瘦撬恨袖足吸驻罕影茸戒华锗硝灌襟昭界膳洋苑收茵屡拈鹏队销鞠闹第20讲组计数第20讲组计数n n作业 习题8.3 (单数或双数)姻镁荔碧搜判藉拴插龚概刻凳糖团慨液剥瘟迭玄塔梗粕裔榆菏疚蘑洱钝徒第20讲组计数第20讲组计数
