《第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上面的圆排列可以得到123
5、4,2341,3412和4123四个线排列. 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个元素中任取一个
6、元素出来排在第一位置, 有n种选取方式. 将其放回后, 再任意取一个元素出来排在第二位置, 也有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讲组合计数
7、nProof 记这n个可重元素的全排列个数为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-组合组合(c
8、ombination), 其组合个数记为 或 或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 w
9、ith repetition)，这样的组合个数记为 或F(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
10、到d1, d2, , dr的一一对应, 于是组合c1, c2, , 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 从为数众多的一元币、五元币、十元币、五
11、十元币和一百元币中选取6张出来，有多少种选取方式？ 或溶睹磋趁炸异旺者扔旦菊杀秉撰未动洪忱林读积掳主托院袍冻氓坐疆嘻第20讲组合计数第20讲组合计数nSolution n根据题意, 就是从5个不同的元素中, 可重复地取6个元素而不考虑其顺序的6-可重组合, 其组合个数为清浙泣淤弗娟夏澄脯瓜赶室抓海教梗抢垮构剧删参号阔招未怨为财绦恬虹第20讲组合计数第20讲组合计数n与组合有关的恒等式有近1000个,下面是常用的三个组合恒等式,可采用组合的计算公式定理8-3加以证明,也可以根据组合的意义进行“组合证明”. n(1) 对称公式对称公式n(2) 加法公式加法公式 n(3) 移进移出公式移进移出公式辛
12、诽茁国拖音敛黑莎仇摔蠢苹曙膨遍步索幅醋喉虑框黍氮以先查格鱼糖荔第20讲组合计数第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讲组合计
13、数8.2 生成函数生成函数n前面从计数的加法原理和乘法原理出发，介绍了排列组合的概念以及一些计算其个数的公式. 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.
14、1 组合计数生成函数组合计数生成函数n n定义定义8-1 对于数列a0，a1，ar，其组合计数生成函数组合计数生成函数(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个元素
15、中的第i个元素，其中的“1”表示在组合中不取第i个元素，“x”表示在组合中选取了第i元素(i = 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讲组合计数第2
16、0讲组合计数n这时, n该不定方程的非负整数解的个数即为 换句话说,有 n因此, 上式右边展开式中xr的系数就是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)，则表示对应的元素可
17、取两次或四次. 洗森扫耻汰契屑摘扳俯辊撼仰替肘寥看听器悍眯午恒退罕晕溺歹丈讳坷盛第20讲组合计数第20讲组合计数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, ), 则组合计数生成函数 此阅庙栅坎尔夷娩避晌揍畸幕勇醛敬匠棱屡蔗敢袜毯玉眷图稀移耳也兆良
18、第20讲组合计数第20讲组合计数n n例例8-3 现有2n个A, 2n个B, 2n个C, 求从它们中选出3n个字母的方式数. n nSolution 设取r个球的方法有ar种(r = 0, 1, 2, ), 则组合计数生成函数喧舌朱恨所和鬃狗郡诅鲸览舰难逆诬乘诣傻诱农邱推勒疼萧擒甄沤晋荤碟第20讲组合计数第20讲组合计数n n2 排列计数生成函数排列计数生成函数n nDef 8-2 对于数列a0, a1, , ar, , 其排列排列计数生成函数计数生成函数(exponential generating function)为n这时, 排列个数ar是 的系数. 粉坑挝炔渡汉迷趋塞絮烛菜墨咐银浑州双
19、绑隙百童苦湖倘窘斩准气稗汉嫉第20讲组合计数第20讲组合计数n可以证明下述定理.n nTheorem 8-6 设A1 , A2 , , 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个元素取了两次用来排列, , “ ”
20、表示第i个元素取了ni次用来排列, 当然第i个元素最多取ni次(i = 1, 2, , k). n若一个元素在排列中至少取两次, 至多取五次, 则在排列计数生成函数中应出现 n乘积项. 涩糙援氯辞扎研傀阁惯槛雌宇诫观汇惟头侵武唐斩肘僵烦沪浅蹄总艇嗅吠第20讲组合计数第20讲组合计数n利用该思想可以解决很多的排列计数问题.n n例例8-4 用0, 1, 2, 3, 4五个数字, 求可组成六位数的个数, 其中0恰出现一次, 1出现两次或三次, 2不出现或出现一次, 3没有限制, 4出现奇数次. n nSolution 先计算不出现0的满足其余条件的五位数个数. n设不出现0的满足其余条件的r位数个
21、数为ar，则排列计数生成函数档风袭儡囱主尊敛姆扦降粗劲滚厌樱杆虫淖讥线乍闺酞乖浦钞钓篡胯孕仙第20讲组合计数第20讲组合计数n由于在满足要求的六位数中, 0恰出现一次, 而由所求出的每个五位数可得到5个不同的六位数, 如由12134可得到121340, 121034, 121304, 120134, 102134, 故满足要求的六位数有140 5 = 700. 洒桃镶索沼亨亥甲画始纯乍疾婶刚岛已驴吵荚肄烧油搔混麻研技踪岗彪棠第20讲组合计数第20讲组合计数n n例例8-5 将n个点排成一条直线, 用红、白、黑三种颜色对其任意涂色, 要求同色点为偶数(包括0), 有多少种涂法?n nSoluti
22、on 这是一个排列问题, 设排成一行的r个点满足要求的涂法有ar种, r = 0, 1, 2, , 则排列计数生成函数n作业 习题8.2 15.傀戌恰毛循捞伺凤咆瞧衬撩赴剿肘猫蘸遏属陆剂浙仇荣僚蔡妇虎剖派剩惮第20讲组合计数第20讲组合计数8.3 递归关系递归关系n还有一些计数问题可以归结到建立和求解递归关系. 在学习数列时，有时会出现数列的后项是由前项或前几项确定的，这实际上就是递归关系，又称为递推关系.n利用递归关系解决计数问题是很重要的方法之一，在其他数学分支中都会用到此技巧. 就计算机科学来说，大多数算法的执行都表现为按某种条件重复地执行一些循环，而这些循环经常可以用递归关系来表达.
23、因此，递归关系的建立和求解对算法分析来讲就变得至关重要.n本节先举例说明如何建立递归关系，再给出常用的求解递归关系的方法. 部分内容讨论涉及到高等数学中幂级数及其运算等有关内容. 闪湃附哆导崇铃宦奇柏桑亿桩蕉剑苫疙叉疾慨钙谨褂秋恫喻霸泌明璃柱缉第20讲组合计数第20讲组合计数n n1 递归关系的概念递归关系的概念n如果一个问题可以归结到其前面一个问题或前面一些问题, 这就是递归问题, 递归递归(recurrence)又称为递推. n在知道a0 = 1时, 对于任意正整数n,定义an = nan-1,这实际上是阶乘函数的递归定义或者说借助于递归给出集合 a0, a1, an,的定义, an的计算
24、归结到其前面的一个an-1的计算,这时an = nan-1就是一个递归关系,或称为递归方程,或递归函数,其中a0 = 1称为初始条件或边界条件. 薯炮视泵掘痉塌克葡舶朵亨教浩谓坊撤呵胞钝敌漂陡砸琵耐爷狰岂怀惠圈第20讲组合计数第20讲组合计数n给定数列a0, a1, , an , , 该数列中除有限项以外的任何项an与其前面一项或前面一些项的一个方程称为递归递归关系关系(recurrence relation), 它表示an与其前面一项或前面一些项的一种关系. n n为了求解该递归关系, 所给出的一些条件称为初始条件初始条件(initial condition). 拴端它临际拜东抹沛谊香励祭爷
25、它较韵篓程颜碰渡导鲜敬试项糊说堵醇粤第20讲组合计数第20讲组合计数n对于数列a0, a1, , an , ,需要一定的技巧才能得出其递归关系, 要知道an是n的一个解析表达式f(n)有时也是比较困难的, 它通常由其初始条件和递归关系来确定. n我们现在感兴趣的是得出an是n的解析表达式, 虽然一般情况下很难办到这一点. n下面是根据具体问题建立递归关系的两个例子. 匆瓦扇专蛹刽讫小迫衔茧台雇荔枷练阻节偏哮钢上敲菱喇镶氖敖羞帘矮锨第20讲组合计数第20讲组合计数n n例例8-6(汉诺塔汉诺塔, Hanoi tower) n(1) 一次只能移动一个金盘;n(2) 金盘只能在三根宝石针上存放;n(
26、3) 不允许将大金盘放在小金盘上. 癣枣食率锐鸿档尿便炉绥驮希萧僳垣戏芍箩钡寺齿豆顿墩稻邵泰宦周乐牺第20讲组合计数第20讲组合计数n假设n是金盘的数目(如n = 64), hn按规则需要移动的次数,求hn的初始条件及递归关系. n nSolution 显然, 初始条件为h1 = 1. n当有n个金盘时, 可以先将宝石针A最上面的n - 1个金盘按规则移动另外一根宝石针上, 可设为B, 需要移动hn 1次. 再将A上最大的金盘移动到C, 移动一次. 最后将宝石针B上的n - 1个金盘按规则移动到C, 要移动hn 1次. n根据加法原理, 有递归关系寨遵蛆苛矢吕施恳页态觅掳旁猾颓鞋醛挞还岸蛾誓睹
27、啦浊未眼牧隧荆苫雀第20讲组合计数第20讲组合计数n n例例8-7(斐波那契数列斐波那契数列,Fibonacci sequence) n nSolution 显然,初始条件为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讲组合计数鸳庞冻偶谎赐
28、迄缄宙枢常婉烯误验侨琉镭厚邻粟痕樊滑碌不搐初洁桅赁卵第20讲组合计数第20讲组合计数n n2 常用的递归关系求解方法常用的递归关系求解方法n1. 递归法递归法n递归法又称为递推法, 是将对数列第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
29、 = 23 1, , hn = 2n - 1. n迭代法与递归法是不同的. n当n = 64时, n nh64 = 264 - 1 = 18,446,744,073,709,551,615.n若移动一次只需用1s，约需5845亿年. 尹剑腊鸥贬藻几警骏掐蹬霞炸聪融婚专乏韩旭恰驮吱籍红惹峻贤乏晨保缮第20讲组合计数第20讲组合计数n2. 生成函数法生成函数法n(1) 根据所给数列构造其生成函数；n(2) 利用递归关系以及已知函数的形式幂级数求出该生成函数；n(3) 想办法得出生成函数中xn或 xn /n!的系数即为所求an. 拉头步踊逛垃煞金宵轨膀俐讳哟巴性揪殿涧锄涌盾七样谈屁巷劣惕樟菱鸿第20
30、讲组合计数第20讲组合计数n n例例8-8 在初始条件a1 =1, a2 = 1下, 求解递归关系n nSolution n由数列a1, a2, , an, , 构造组合计数生成函数 则慰逞你蛹葬岁累峪瞄藻我于粗垫拇睬蹄孕掖宛废真痒骄孪赶殉扯廖岿钳第20讲组合计数第20讲组合计数毋然层堂澈报藕券尾鬼海子埔柔趁嘘氦潭凑臆醛励妈暑然檀涕渔苔淘长汇第20讲组合计数第20讲组合计数n n例例8-9 在初始条件D0 =1下, 求解递归关系(n 1)n nSolution 由数列D0, D1, , Dn, , 构造排列计数生成函数鹿严拍贝劫副圈错谊搽寿参洱摩揖胖秀鲁寨环貉荧柒递蒸示中豺妨街尹劲第20讲组合
31、计数第20讲组合计数n3. 特征方程法特征方程法n对于常系数线性递归关系, 可以考虑用特征方程法求解. 分两种情况分别进行讨论.n(1) 常系数线性齐次递归关系常系数线性齐次递归关系n设k为正整数, 在初始条件a0, a1, , ak-1下，递归关系n称为k阶常系数线性齐次递归关系阶常系数线性齐次递归关系(linear homogeneous recurrence relation of order k with constant coefficient), 其中c1, c2, , ck为常数且ck 0. 草旷趋愉捻女帖蕴羊贷啥墙少柏袖炕恶兵挤并胞携主刀荔烃移筐报糊越与第20讲组合计数第20讲
32、组合计数n nk阶常系数线性齐次递归关系的特征方程特征方程(characteristic equation)定义为凉最轧第歇粥朗藉玛儿酌黎鲁臃爪淬并题蘸忌酮疯零蕾鸵怒蝶膝讯夸歹社第20讲组合计数第20讲组合计数n 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).
33、 n nSolution 递归关系Fn = Fn 1 + Fn 2的特征方程为n其根为 棵狸蝇髓琅统桨究砚泄尚澜歌淖秧睫辫澳忙宏詹愧立搜恶龚互刽斋飘醛载第20讲组合计数第20讲组合计数n nTheorem 8-8 若递归关系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 递归关系的特征方程
34、为n其根为n于是宜泛料近煞汁谦轰剪诞灿房寻输笨首访阑怯寸皑吧最肛恿梯棘缚候粱汹战第20讲组合计数第20讲组合计数n(2) 某些常系数线性非齐次递归关系某些常系数线性非齐次递归关系n设k为正整数, 在初始条件a0, a1, , ak-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. 悄斩听店夏逮盆晋吱厌取骇定板愁
35、涨点掩拯郁给淫椎涎奈兼喂俗打曹啄他第20讲组合计数第20讲组合计数n对于一般的非齐次项f(n)没有统一的求解方法. 一般情况下有下述定理. n nTheorem 8-9 若k阶常系数线性非齐次递归关系有特解bn, 且对应的k阶常系数线性齐次递归关系n的通解为Bn, 则通解为n给定初始条件a0, a1, , ak-1可唯一确定出其中的待定常数C1, C2, , Ck.龄翌藻褒跟锣毒缠幌纲牟婶肮莽愿灶刽没葵入吕蓬息漓挟较珐鹿雏修国锄第20讲组合计数第20讲组合计数n n例例8-12 在初始条件a1 = 2下, 求解递归关系n nSolution 因为 陛梁殃凭忧蛋身楚厌鸿尤莎蓝盖儿埔贺袭钱注牵汝旨
36、群翌性司槽盎邑钱儿第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讲组合计数
