组合数学复习

1、组合数学组合数学Mathematics ModelingLianyungang第第 1 章章 什么是组合数学什么是组合数学第第 2 章章 鸽巢原理鸽巢原理第第 3 章章 排列与组合排列与组合第第 4 章章 二项式系数二项式系数第第 5 章章 容斥原理及应用容斥原理及应用第第 6 章章 递推关系递推关系第第 7 章章 生成函数生成函数第第8章章 Polya定理定理内 容组合数学2第第1章章 什么是组合数学什么是组合数学Mathematics ModelingLianyungang根本问题根本问题存在条件存在条件安排的个数安排的个数枚举分类枚举分类性质和结构性质和结构找出一定条找出一定条件下的最优

2、件下的最优安排安排四四 类类 问问 题题存在问题存在问题计数分类计数分类分析问题分析问题优化问题优化问题组合数学4Mathematics ModelingLianyungang是研究离散结构的存在、计数、是研究离散结构的存在、计数、分析和优化等问题的一门学科。分析和优化等问题的一门学科。什么是组合数学什么是组合数学?组合数学5Mathematics ModelingLianyungang组合数学6棋盘完美覆盖问题棋盘完美覆盖问题Mathematics ModelingLianyungangm n 棋盘有完美覆盖棋盘有完美覆盖 iff m 和和 n 中至少中至少有一个是偶数。有一个是偶数。当当

3、m 是偶数时，每块多米诺骨牌竖放。是偶数时，每块多米诺骨牌竖放。当当 m 是奇数且是奇数且 n 是偶数时，每块多米诺骨是偶数时，每块多米诺骨牌横放。牌横放。当当 m 和和 n 都是奇数时，棋盘的方格数都是奇数时，棋盘的方格数 mn 是奇数。是奇数。棋盘完美覆盖问题棋盘完美覆盖问题组合数学7Mathematics ModelingLianyungang构造问题构造构造 n 阶幻方的方法，其中阶幻方的方法，其中 n 是奇数。是奇数。1.将将 1 放在第一行中间。放在第一行中间。2.自左下至右上沿对角线顺次自左下至右上沿对角线顺次放随后各数，将最后一行认为放随后各数，将最后一行认为是第一行上面的行，

4、第一列认是第一行上面的行，第一列认为是最后一列右面的列。为是最后一列右面的列。3.若要放数的位置已有数，则若要放数的位置已有数，则将数放在原数下方。将数放在原数下方。294753618Mathematics ModelingLianyungang作业作业Part1: Ch1: 1，2，Mathematics ModelingLianyungang1.组合数学是研究什么的学科？2.组合数学研究中的四大问题是什么？温习Mathematics ModelingLianyungang第 2 章 鸽巢原理组合学原理：鸽巢原理：简单形式鸽巢原理：加强形式Mathematics ModelingLianyu

5、ngang鸽巢原理：简单形式【定理定理】 若将 n+1 个物体放入 n 个盒子，则至少有一个盒子中的物体数大于 1。鸽巢原理应用【问题】设 n 是正整数，必存在由数字 0 和 7 组成的正整数能被 n 整除。整除的数。是能被 ，000777差 为除余数相同。则余数相被777和777，除余数相同。设被种可能，所以必有两数余数只有除被 个不同正整数，1是777，77，7证明个个个个个1nnjinnnniijjin则这鸽子：n+1个数；巢：n个余数一人每天至少看1h电视，总共看7周，但每周最多看11h试证明存在连续若干天，在此期间他恰好看电视20h（假设看电视时间是整数个小时）. Mathemati

6、cs ModelingLianyungang鸽巢原理：加强形式【定理定理】 设 q1, qn 是正整数，将 q1 + + qn n + 1个物体放入 n 个盒子，或者第 1 个盒子中至少有 q1 个物体，或者第 n 个盒子中至少有 qn 个物体。 q1+ + qn n +1=(q1-1)+(q2-1)+(qn -1)+1证明证明 否则物体总数至多q1 1 + + qn 1 = q1+ + qn n 取 q1= = qn = 2，就退化为简单形式的鸽巢原理。Mathematics ModelingLianyungang鸽巢原理：加强形式设 q1, qn 都等同于一个正整数 r。1.将 q1 +

7、+ qn n + 1=n(r-1)+1 个物体放入 n 个盒子，则至少有 1 个盒子含有 r 个物体或更多。2. 如果 n 个非负整数的平均数大于 r-1， 那么至少有一个整数大于或等于 r。3.如果 n 个非负整数的平均数小于于 r+1， 那么至少有一个整数小于r+1。Mathematics ModelingLianyungang鸽巢原理：加强形式应用 一篮子水果装有苹果、香蕉和橘子。为一篮子水果装有苹果、香蕉和橘子。为了保证篮子或者至少了保证篮子或者至少 8 个苹果或者至少个苹果或者至少 6 个香蕉或者至少个香蕉或者至少 9 个橘子，则放入篮个橘子，则放入篮子中的水果的最小件数是多少？子中

8、的水果的最小件数是多少？8+6+9-3+1=21Mathematics ModelingLianyungang今有12只鸽子飞进5个笼子，则必有有一个笼子，该笼子里至少有几只鸽子 ？由鸽笼原理：31511211nm Mathematics ModelingLianyungang作业Part1: ch2: 3，4，9，15, 16Mathematics ModelingLianyungang温习1.什么是鸽巢原理？2.是解决组合数学中的哪个问题？3.每人设计一个鸽巢原理的应用。4.班平均成绩80,则一定有一个人的成绩大于等于80。这个判断应用的是什么原理。5.组合数学中研究的第二大问题是什么？M

9、athematics ModelingLianyungang第 3 章 排列与组合1.计数原理2.集合的排列3.集合的组合4.多重集的排列5.多重集的组合Mathematics ModelingLianyungang基本的计数原理加法原理：乘法原理：减法原理相等原理Mathematics ModelingLianyungang加法原理如果有 p 种方法能够从一堆中选择一个物体，而有q 种方法能从另一堆中选择一个物体，那么从两堆中选择一个物体的方法一共有 p+q 种。应用应用：有 5 种蔬菜和 4 种水果选择，每天吃一种蔬菜或一种水果的选择有多少种？5+4=9Mathematics Modeli

10、ngLianyungang乘法原理如果第一项任务有 p 个结果， 第二项任务有 q 个结果，则这两项任务连续执行有 p q 个结果。应用：应用：每日吃5种蔬菜和4水果的选择有多少种？若每日还要吃r种主食有多少种选择？5 4=205 4 r=20r排列数的计算公式!)(!)1()1(),(， 则若3.2.1定理rnnrnnnrnPnrMathematics ModelingLianyungang应用：应用： 26个字母排列。要求元音不得相继出现，求排列的总数。个字母排列。要求元音不得相继出现，求排列的总数。解：辅音：解：辅音：21个，辅音字母的排列个，辅音字母的排列 21!个个 元音的位置空间元

11、音的位置空间22个个a：22个位置个位置 e: 21个位置个位置 i: 20个位置个位置 o: 19个位置个位置 u: 18个位置个位置共有共有P(22, 5)=22！/17!则根据乘法原理，元音不相继出现的排列为则根据乘法原理，元音不相继出现的排列为21! 22!/17!Mathematics ModelingLianyungang 1）由两个英文字母后接四个数字来组成汽车牌照，问不同的牌照有多少种？2）如果两个英文字母必须不同，组成的牌照又有多少种？ （1）262104（2）P(26,2) 104循环排列数定理定理3.2.2 n 元集的元集的 r 循环排列数为循环排列数为 n 元集的循环元

12、集的循环 n 排列数为排列数为 (n 1) ! 。!)(!),(rnrnrrnPMathematics ModelingLianyungang例例 10 男生 5 女生围圆桌聚餐，任何两个女生不相邻的坐法有多少种？解解 男生先坐好，有 9！种坐法。固定一种男生坐法，然后让女生插入10 个空档，女生之间还存在排序问题，故有 P (10, 5) 种排法所以，共有 9! P (10, 5) 种坐法。Mathematics ModelingLianyungang例例 10 人围坐一圆桌，其中甲、乙两人不愿挨着坐，共有多少种坐法？解解 若不考虑甲和乙是否挨着，有 9! 种坐法。若甲固定坐在乙左边，可将甲

13、和乙看作一人，有 8 ! 种坐法。若甲固定坐在乙右边，也有 8 ! 种坐法。所以，满足条件的坐法有 9! 2 8 ! 种。Mathematics ModelingLianyungang n对夫妻围圆桌就坐，要求每对夫妻不相邻，问有多少种入座方式？ 解 将n个丈夫记为，他们的妻子分别记为，设性质pi表示xi与yi相邻，其中i=1,2,n.令S为2n个人的全体环排列构成的集合，S的满足性质pi的子集Ai，i=1,2,n.那么有由包含排斥原理得到)!1(2|.1)!32(2|,.,2 , 1,)!22(2|)!12(|212nAAAnjinAAninAnSnnjii23(21)!2(22)!2 (2

14、3)!2 (24)! .( 1)2 (1)!123nnnnnnNnnnnnn Mathematics ModelingLianyungang3.3 集合的组合集合 S 的 r 组合即为 S 的 r 元子集，将 n 元集的r 组合数记为。rn! )( !),(!),(01.3.3定理1100rnrnrrnPrnrnrrnPnrnnnnnrnnr因此，对于。，。，则若rnnrn定理定理3.3.2 nnnnn210Mathematics ModelingLianyungang某班有男生 21人，女生 14人，需选举 4 人组成班委会，要求班委会有男有女，可能有多少种选举结果？解法一解法一 班委会有

15、i 个女生的选举结果有 种，选举结果总数为解法二解法二 若不要求班委会有男有女，则选举结果数为 ，所求数为ii42114453744211431iii43545374414421435Mathematics ModelingLianyungang温 习1.P(n,r) 表示什么？ 表示什么？2.P(n,r)和 之间的计算关系是什么？3.P(n,n)=? =？4.n元集合的循环n排列=？rnrnnnrnMathematics ModelingLianyungang3.4 多重集的排列定理定理3.4.1 多重集 S = a1, a2, ak的 r 排列数为 k r。的全排列数为，则多重集设!,3.

16、4.2定理21111kkkknnnnananSnnnMathematics ModelingLianyungang定理定理3.5.1 多重集 S = a1, a2, ak的 r 组合数为111kkrrkr应用：求 S =9a, 9b, 9c, 9d 的使得每种元素至少出现一次的 9 组合个数。令 y1 = x1 1， y2 = x2 1， y3 = x3 1， y4 = x4 1(x1, x2, x3, x4) 是 x1+ x2+ x3+ x4 = 9 的正整数解iff (y1, y2, y3, y4) 是 y1+ y2+ y3+ y4 = 5 的非负整数解 S 的满足条件的 9 组合个数=

17、x1+ x2+ x3+ x4 = 9 的正整数解个数= y1+ y2+ y3+ y4 = 5 的非负整数解个数56!36783814145Mathematics ModelingLianyungang作业Ch3： 6,10,11,13,15,17,27,30Mathematics ModelingLianyungang温 习1. 什么是多重集？2. 无穷 k 种元素 r 排列的个数？3. n 个 k 种元素的全排列？4. 无穷 k 种元素r 组合的个数？Mathematics ModelingLianyungang第 四 章 二项式系数4.1 二项式定理4.3一些恒等式4.2牛顿二项式定理4.

18、4非降路径法4.5多项式定理定理定理4.2.1 设 n 是正整数，则4.1 二项式定理nkkknnyxknyx0)(nkknkknxknnxknxn00)1 (5.2.2定理为非负整数，设4.2 一些恒等式111knknknknnkn0)1(121)1(000nkknnknkknknxknxxknx，得令，得令Mathematics ModelingLianyungang1211nnknknnk其中nknnkknnkknknknxxknkxnxxknx11111021)1 ()1 (令求导数两边对2证法Mathematics ModelingLianyungang证明11211.2311211

19、1nnnnnnn证明：证明：将等式两边对将等式两边对x从从0到到1积分得积分得即即得证。得证。 011000111100010(1)(1)(1)1121111nnkknnkknknknnknxxknxdxx dxkxxnknknknkMathematics ModelingLianyungang)2)(1(32)2)(1(1)2)(1(11212111111)1 (1111)1 ()1 (,)1 ()2)(1(12002100110101100000 nnnknkkknkknndxxknkdxnxxknknxdxxkndxxxknxknkknnknknnkknnkknxnkkxnnkknnk2

20、解法求Mathematics ModelingLianyungangnknknnknknnknnnnSknknnBkknAknBkAnSBASbbBaaA020112)()(,2组合数的组合，个有组合，个有组合合并而成的组合与的组合由的，设证法nnknnk202Mathematics ModelingLianyungang证明组合恒等式的方法1.用组合数公式直接验证。2.用数学归纳法。3.分析恒等式的组合意义。4.利用二项式定理，对公式进行微分或者积分运算。5.利用二项式定理，比较多项式的系数。Mathematics ModelingLianyungang4.5 多项式定理knknknanan

21、annnnnnnnntnnnnnnnntttttt二项式系数的全排列数。是多重集其中定义多项式系数,2!221121212121Mathematics ModelingLianyungang作业 第四版 7, 11，12，16.Mathematics ModelingLianyungang第 5 章 容斥原理及应用5.1 容斥原理5.2 具有重复的组合5.3 错位排列5.4 带有禁止位置的排列Mathematics ModelingLianyungang11 , 1,21111 , , 1, 31,1, 115.1.1,|( 1) |( 1)|iii jmmmmiijimijkmi j kmm

22、ikkikkmimmAASAASAAAAAAAASAAAASAA 是的 合是的 合是的 合定理若是集合 的子集，Mathematics ModelingLianyungang求不连续出现 MATH, IS, FUN 的集合 U = M, A, T, H, I, S, F, U, N的排列数。解解 令 S 为 U 的所有排列的集合，A1为连续出现 MATH 的排列的集合， A2 为连续出现 IS的排列的集合， A3 为连续出现 FUN 的排列的集合。A1中的排列是 MATH, I, S, F, U, N的排列，A2 中的排列是 M, A, T, H, IS, F, U, N的排列， A3 中的排

23、列是 M, A, T, H, I, S, FUN的排列， | S | = 9! ，| A1| = 6! ，| A2| = 8!， | A3| = 7!A1 A2中的排列是 MATH, IS, F, U, N的排列，A1 A3中的排列是 MATH, I, S, FUN的排列，A2 A3中的排列是 M, A, T, H, IS, FUN的排列，|A1 A2 | = 5!，|A1 A3 | = 4!，|A2 A3 | = 6!，A1 A2 A3中的排列是 MATH, IS, FUN的排列， |A1 A2 A3 | = 3!31765836457869|321323121321321！AAAAAAAA

24、AAAASAAA求1到1000之间不能被5 ，6 ，或8整除的自然数的个数 解：解：用用lcma1,a2,an表示表示n个整数个整数a1,a2,an的最小公倍数。的最小公倍数。设设S=1,2,1000，令，令A,B,C分别为分别为11000中能被中能被5,6,8除尽的整数集合。除尽的整数集合。显然，其补集代表不具备被整除性质的集合。根据题意有显然，其补集代表不具备被整除性质的集合。根据题意有根据容斥原理，不能被根据容斥原理，不能被5,6,8中任何一个数整除的数目为中任何一个数整除的数目为|S|A|B|C|AB|BC|CA|ABC|ABC|1000100010001000,200,166,125

25、5681000100033,41,lcm5,6lcm6,81000100025,8lcm8,5lcm5,6,81000(200166125)(334125)86005.2 具有重复的组合考虑某些元素的重数为正整数的多重集的组合数。rkr1试确定多重集的 组合数 123=1,kSaaaa解：解：把把S的的r-组合分成两类：组合分成两类： 包含包含a1的的r-组合：这种组合数等于组合：这种组合数等于*a2,*ak的的(r1)-组合数，即组合数，即 N1=C(k-1)+(r-1)-1, r-1)=C(k+r-3, r-1). 不包含不包含a1的的r-组合组合：这种组合数等于这种组合数等于*a2,*a

26、k的的r-组合数，即组合数，即 N2=C(k-1)+ r-1, r )=C(k+r-2, r). 由加法法则，所求的由加法法则，所求的r组合数组合数 N=N1+N2=C(k+r-3, r-1)+C(k+r-2, r).一糕点店生产8种糕点，若一盒内装有12块各种糕点，并且可认为每种糕点无限多，则你能买到多少种不同的盒装糕点（假设装盒与顺序无关）？ 1238,saaaa 128 119503881212N 这是一个组合问题，即的12-可重组合,所以 确定 T = 3a, 4b, 5c的 10 组合数。解法解法1（用容斥原理）令 T * = a, b, c，S 为 T * 的 10 组合的集合，A

27、1 为至少有 4 个 a 的 T * 中 10 组合的集合，A2 为至少有 5 个 b 的 T * 中 10 组合的集合，A3 为至少有 6 个 c 的 T * 中 10 组合的集合。6621112212101310|SMathematics ModelingLianyungang合数4的组合数10的个6的至少有|组合，10的个6组合得到至少有4的加到个6将；21267275135组合数5的组合数10的个5的至少有|组合，10的个5组合得到至少有5的加到个5将；28278286136组合数6的组合数10的个4的至少有|组合，10的个4组合得到至少有6的加到个4将*3*

28、2*1*TcTAcTcTbTAbTbTaTAaTaMathematics ModelingLianyungang61315212866|0|0|1|3|32132132*31*21*AAATAAAAAcbTAAcaTTbaTAAbaTba组合数的。；组合，的个和个没有至少有；组合，的个和个只有一个至少有；组合数的组合数的个和个的至少有组合，的个和个至少有组合得到的加到个和个将1010651064110541054154Mathematics ModelingLianyungang求方程 x1+ x2+ x3+ x4 = 18 满足1 x1 5, 2 x2 4, 0 x3 5, 3 x4 9 的

29、整数解的个数。解法解法1 做变量代换：y1= x1 1, y2 = x2 + 2, y3 = x3, y4= x4 3, 方程： y1+ y2+ y3+ y4 =16 (1)约束条件：0 y1 4, 0 y2 6, 0 y3 5, 0 y4 6 令 S 是方程 (1) 的所有非负整数解的集合，A1 , A2, A3, A4 分别是满足 y1 5, y2 7, y3 6, y4 7的方程 (1) 的整数解的集合，Mathematics ModelingLianyungang2206101112312141499|,7364612131431414141111|,59696171819319141

30、416|43212224321111的非负整数解的个数方程令的非负整数解的个数方程令yyzyAyzyyyzAyzSMathematics ModelingLianyungang2206101112312141499|,7286611121331314141010|,643214444321333的非负整数解的个数方程令的非负整数解的个数方程令zyyyAyzyzyyAyzMathematics ModelingLianyungang356567373144|475566678383145|565356567373144|4757:6:7:5:414321441131432133112143212

31、21144332211AAzyyzyzyzAAyzyzyzyzAAyyzzyzyzyAyAyAyAMathematics ModelingLianyungang206456363143|37610245252142|277206456363143|3677:6:7:5:43432144334243214422324321332244332211AAzzyyyzyzAAzyzyyzyzAAyzzyyzyzyAyAyAyAMathematics ModelingLianyungang55201020355635)220286220364(969|0|0|,34, 3,2, 17:6:7:5:164

32、3214321443322114321AAAAAAAAAAAkjiyAyAyAyAyyyykji，组合的每个对于Mathematics ModelingLianyungang5.3 错位排列若 i1 a1，in an，则称 a1, an 的全排列 i1in 为错位排列，或简称为错排。用 Dn 表示 1, n 的错位排列的个数。!)1(!111!)1(!1.3.60nnknDnnkkn定理%8.36!1ennDn充分大时，这个概率是当，错位排列的概率为Mathematics ModelingLianyungangDn 满足的递推关系Dn = (n 1) ( Dn2 + Dn1 ) n 2Dn =

33、 n Dn1 + (1)n n 1定理定理5.4.1 p (X1, Xn)= n! r1(n 1)! + + (1)n rn其中 rk 表示将 k 个非攻击车放在禁止位置的方法数。求 p (1,1,2,3,4,3,4, , ) r1 = 7F1F2r2 = 1 + 2 + 3 4 = 15r3 = 1 4 + 3 2 = 10r4 = 1 2 = 2r5 = r6 = 0p (1,1,2,3,4,3,4, , )= 6! 7 5! + 15 4! 10 3! + 2 2! = 184 用四种颜色（红、蓝、绿、黄）涂染四台仪器A,B,C和D规定每台仪器只能用一种颜色并任意两台仪器都不能相同如果B

34、不允许用蓝色和红色，C不允许用蓝色和绿色，D不允许用绿色和黄色，问有多上种染色方案？ A B C DGLWY解：解：由题意，可得棋盘如右图，其中有阴影由题意，可得棋盘如右图，其中有阴影的格子表示禁区。的格子表示禁区。由上述可知由上述可知R( )=1+6x+10 x2+4x3，即，即r1=6，r2=10，r3=4，故所求方案数为，故所求方案数为4!-6 3!+10 2!-4 1!=4*Mathematics ModelingLianyungang作业1，4，7，12，24 ii）Mathematics ModelingLianyungang温 习1.写出三个集合的容斥原理（两种形式）2.什么是错

35、排？3.1,2,n的错排Dn=？Dn的递推公式是什么？4.pX1,X2,Xn是什么？等于什么？Mathematics ModelingLianyungang第 6 章 递推关系和生成函数6.2 线性齐次递推关系6.3 非齐次递推关系6.4 生成函数6.5 递推和生成函数Mathematics ModelingLianyungang6.2 线性齐次递推关系k 阶递推关系，由某项前 k 项的值得出该项的值。hn = a1hn1 + a2hn2 + + ak hnk + bn （n k）其中 ak 0, a1, ak , bn 与 hi 无关称它为 k 阶线性递推关系。若 bn= 0，称它为齐次的。

36、若 a1, ,ak 是常数，称它为常系数的。Mathematics ModelingLianyungangDn = (n 1) (Dn 1 + Dn 2)2 阶线性齐次Dn = n Dn1 + (1)n1 阶线性非齐次fn = fn1 + fn22 阶线性齐次常系数n ! = n (n 1)! 1 阶线性齐次hn = q hn 11 阶线性齐次常系数hn = hn 1 + q 1 阶线性常系数hn = hn 1 hn 22 阶非线性齐次求解常系数线性齐次递推关系hn = a1hn1 + a2hn2 + + akhnk ( n k, ak 0 )h0 = b0 , h1 = b1 , , hk

37、1= bk 1xk a1xk1 a2xk2 ak = 0 （特征方程）若有 k 个不同特征根 q1 , q2 , , qk ，则通解为nkknnqcqch11Mathematics ModelingLianyungang111111110111110kkkkkkkknkknnbqcqcknbqcqcnbccnqcqchMathematics ModelingLianyungang求由 a, b, c 组成的不连续出现 a 的长度为 n 的字的个数 hn 。h0 = 1 (空字)， h1 = 3，h2 = 8 （去掉 aa）考虑由 a, b, c 组成的不连续出现 a 的长度为 n 的字：若首字

38、母是 b 或 c ，其余部分有 hn1 种选择；若首字母是 a ，第二个字母可以是 b 或 c ，其余部分有 hn2 种选择。hn = 2hn1 + 2hn2Mathematics ModelingLianyungang3232323233131110313131310223122212121212121021ccccnccncchqqxxhhhhhnnnnnn，解得通解，特征根特征方程，Mathematics ModelingLianyunganghn = hn1 + 3hn2 + 5hn3 + 2hn4 （n 4）h0 = 1， h1 = 0，h2 = 1，h3 = 2 特征方程 x4 +

39、 x3 3x2 5x 2 = 0 x4 + x3 3x2 5x 2= x4 2x3 + 3x3 6x2 + 3x2 6x + x 2 = (x 2)(x3 + 3x2 + 3x + 1)= (x 2)(x + 1)3 特征根 q1 = 1（3 重根）q2 = 2Mathematics ModelingLianyunganghn = hn1+ 3hn2 + 5hn3 + 2hn4 （n 4）h0 = 1 ， h1 = 0，h2 = 1, h3 = 2 特征方程 x4 + x3 3x2 5x 2 = 0特征根 q1 = 1（3重根）q2 = 2通解hn = (c1+ c2n + c3n2)(1)n

40、 + c42nn = 0c1 + c4 = 1n = 1 c1 c2 c3 + 2c4 = 0n = 2c1 + 2c2 + 4c3 + 4c4 = 1n = 3 c1 3c2 9c3 + 8c4 = 292433129710cccc，解得Mathematics ModelingLianyungang猜测非齐次递推关系的特解 hnbn是 n 的 s 次多项式，1是特征方程的 m 重根hn= asns+m + + a0nm求解hn = 6hn1 9hn2 + 2n h0 = 1, h1 = 0特征方程 x2 6x + 9 = 03 是 2 重特征根。设非齐次递推关系特解hn = rn + srn

41、 + s = 6r(n 1) + s 9r (n 2) + s + 2n = (2 3r)n + 12r 3sr = 2 3r, s = 12r 3s 2321srMathematics ModelingLianyungang232632361210233112300, 123233332321211102121nnhccccncnhhnncchnccnnnnnnnn最后结果解得非齐次递推关系通解对应齐次递推关系通解重特征根，是Mathematics ModelingLianyungang解递推关系 （ ） 解：对应的特征方程为 ：特征根分别： ,原递推关系的通解为： 把 ， 代入解得： 原递

42、推关系的通解为： 1201564,9.nnnaaaaa，2n0652 xx122,3xxnnncca3221014,9aa93242121cccc1321ccnnna323Mathematics ModelingLianyungang解递推关系解：因为特征方程为 ,得特征根为2,3 ,所以原递推式对应的齐次递推式： ，有通解为： , 而由P88定理3.17知原递推式有特解为 ,代入原递推式得C=1,D=2,因此原递推式有通解为 ,再将 ,代入通解得 A=2,B=1,所以 12015623,5,10.2nnnaaanaan256xx1256nnnaaa23nnnaABnaCnD232nnnaAB

43、n015,10aa1232nnnanMathematics ModelingLianyungang递推关系 的特征方程有重根2，求它的一般解( )4 (1)4 (2)f nf nf nMathematics ModelingLianyungang求 13 + 23 + + n3令 hn= 13 + 23 + + n3 ，则 hn = hn1 + n3， h0= 0若设特解 hn = rn3 + sn2 + tn + p，则rn3 + sn2 + tn + p= r(n1)3 + s(n1)2 + t(n1) + p + n3两边 n3 的系数相等r = r + 1矛盾1 是特征方程 x 1 =

44、 0 的 1 重根，设特解 hn = rn4 + sn3 + tn2 + pn， rn4 + sn3 + tn2 + pn= r(n 1)4 + s(n 1)3 + t(n 1)2 + p(n 1) + n3n = 00 = r s + t pn = 1r + s + t + p = 1n = 1r s + t p = 16r 8s + 4t 2p 1n = 216r + 8s + 4t + 2p = r + s + t + p + 84)1(424,0,01424110412141222340234nnnnnhchcnnnhptsrnnn通解重根，是特征方程的解得Mathematics Mo

45、delingLianyungangmmnnnnmnnnmnnnxxnmmmmmxxxhhhhxhxhxhhxghhh)1 (,1,011, 1, 1,)(,0001002210210的生成函数是的生成函数是的生成函数是多项式序列级数。不区分函数和它的泰勒的生成函数定义为序列记住记住Mathematics ModelingLianyungangkknneeeeeennnknxnnnnxxxxxxnknhhnknhneehenxxxnkk)1(11,1!1101)1(,1,000000101002211的生成函数则的非负整数解的个数，为设的生成函数是，！，！的生成函数是44040133220222

46、20120220)1(6),2)(1(,6,0)1(6)2)(1()1(6)2)(1()1(2)1(24)1(22)1)(2()1(2)1(12)2(111xxnnnxxxnnnxxxnnnxxxxxxxnnxxxxxxxxnxxxxxxnnnnnnnnnnnn的生成函数为序列得到两边乘两边再求导数得两边再求导数得两边求导数得得到，两边乘Mathematics ModelingLianyungang)1ln(11ln,1,31,21, 1,011ln)1ln(0)1ln(113121111103202xxnxxxxxdxxnxxxxdxxxxxxnxn的生成函数为序列两边求积分Mathemat

47、ics ModelingLianyungang前几章讨论过三种类型的组合问题：1. 求a1, ak的 r-组合数，2. 求a1, ak的 r-组合数，3. 求3a, 4b, 5c的10-组合数。可以将a1, ak的 r-组合看作满足条件n10, 1, nk0, 1的a1, ak的 r-组合 n1a1, nk ak 。可以将 3a, 4b, 5c 的10-组合看作满足条件x0, 1, 2, 3, y0, 1, 2, 3, 4, z0, 1, 2, 3, 4, 5的 a, b, c 的 10-组合xa, yb, zc。并用生成函数统一处理。rnnMnMnxxxxxxxxhhhMhananrMnMn

48、aakkknnrkiMmmMmmMmmkiMmmkiMmmirkkkkkkikii 11111121011111,2, , 1,0,11得出，其中由中的证明。的生成函数为，则序列每个，其中的数目为组合的的满足条件设多重集定理的生成函数。是序列，即的系数是中的的解的数目，所以的方程是满足条件,2101101111hhhxxhxhxxrnnMnMnhkiMmmkirrrMmmrrkiMmmkkkriii Mathematics ModelingLianyungangkrkkrkrhxkkixkknxnknxxxxxxxxxghhhkiMhraarkiinknnnkkkkkiikiiirk2112011111)1