组合数学(西安电子科技大学(第二版))第二章母函数_版24样版

组合数学第2章答案2.1 求序列{0，1，8，27，…3n …}的母函数。

解：()()++++++=++++++=nn n x n x x x x G x a x a x a x a a x G 3323322102780()46414321313=+-+--==-----n n n n n n n a a a a a n a n a左右同乘再连加：464:0464:0464:0464:4321543211123455012344=+-+-=+-+-=+-+-=+-+-----------n n n n n n n n n n n n a a a a a x a a a a a x a a a a a x a a a a a x母函数：()()42162036-+-=x x x x G2.2 已知序列()()3433{,,……()33,,n +……}，求母函数。

解：1(1)nx -的第k 项为：11()k n n +-- ，对于本题，n=4， ∴母函数为：41(1)x -2.3 已知母函数G （X ）=25431783x x x--+,求序列{ n a }解：G （X ）=)61)(91(783x x x +-+=)61()91(x Bx A ++-从而有： ⎩⎨⎧-==⇒⎩⎨⎧=-=+4778963B A B A B A G （X ）=)61(4)91(7x x +-+-G （X ）=7)999x (13322 ++++x x -4))6((-6)(-6)x (13322 +-+++x xn a =7*n )6(*49n -- 2.4．已知母函数239156xx x ---，求对应的序列{}n a 。

解：母函数为239()156x G x x x -=--39(17)(18)xx x -=+- A BG(x)17x 18xA(18x)B(17x)39x=++--++=-令 A B 38A +7B =9+=⎧⎨--⎩解得：A=2 B=1所以 ii i 0i 021G(x)2*(7x)(8x)17x 18x ∞∞===+=-++-∑∑n n n a 2*(7)8=-+2.5 设n n F G 2=，其中F n 是第n 个Fibonacci 数。

习题三（递推关系）1．解下列递推关系：（1）120171000,1n n n a a a a a ---+=⎧⎨==⎩ （2）12016900,1n n n a a a a a --++=⎧⎨==⎩ （3）20100,2n n a a a a -+=⎧⎨==⎩ （4）120121n n n a a a a a --=-⎧⎨==⎩ （5）123012990,1,2n n n n a a a a a a a ---=+-⎧⎨===⎩ 解：（1）对应的特征方程为：27100x x -+=，解得122,5x x ==。

所以齐次递推方程的通解为：25n n n a A B =+，代入初始条件，得：00a A B =+=，1251a A B =+=，解得：11,33A B =-=， 故 112533n n n a =-+。

（2）对应的特征方程为：2690x x ++=，解得：123x x ==-，所以，齐次递推方程的通解为：()(3)n n a A Bn =+-，代入初始条件，00a A ==，1()(3)1a A B =+-=，解得：10,3A B ==-，故1(3)3n n a n =--。

（3）对应的特征方程为：210x +=，解得：12,x i x i ==-，所以，齐次递推方程的通解为：()()n n n a A i B i =+-，代入初始条件，00a A B =+=，12a A i B i =-=，解得：,A i B i =-=，故 11()()n n n a i i --=+-。

（4）对应的特征方程为：2210x x -+=，解得：121x x ==，所以，齐次递推方程的通解为：n a A Bn =+，代入初始条件，01a A ==，11a A B =+=，解得：1,0A B ==，故 1n a =。

（5）对应的特征方程为：32990x x x --+=，解得：1231,3,3x x x ===-，所以，齐次递推方程的通解为：3(3)n n n a A B C =++-，代入初始条件，00a A B C =++=，1331a A B C =+-=，2992a A B C =++=， 解得，111,,4312A B C =-==-，故 1113(3)412n n n a -=-+--2．求由A ，B ，C ，D 组成的允许重复的排列中AB 至少出现一次的排列数。

第二章 母函数及其应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法是比较麻烦的（参见表2.0.1）。

新方法：母函数方法，问题将显得容易多了。

其次，在求解递推关系的解、整数分拆以及证明组合恒等式时，母函数方法是一种非常重要的手段。

母函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转化为多项式或幂级数之间的运算。

2.1 母 函 数（一）母函数（1）定义定义2.1.1 对于数列{}n a ，称无穷级数()∑∞=≡0n nnxax G 为该数列的（普通型）母函数，简称普母函数或母函数。

（2）例例2.1.1 有限数列C (n ,r )，r ＝0,1,2, …,n 的普母函数是()nx +1。

例2.1.2 无限数列{1，1，…，1，…}的普母函数是+++++=-nxx x x2111（3）说明● n a 可以为有限个或无限个； ● 数列{}n a 与母函数一一对应，即给定数列便得知它的母函数；反之，求得母函数则数列也随之而定；例如，无限数列{0，1，1，…，1，…}的普母函数是 +++++n x x x 20＝xx -1● 这里将母函数只看作一个形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”，而且始终认为它是可“逐项微分”和“逐项积分”的。

（4）常用母函数（二）组合问题（1）组合的母函数定理2.1.1 组合的母函数：设{}m m e n e n e n S ⋅⋅⋅=,,,2211 ,且n 1＋ n 2＋…＋ n m ＝n ，则S 的r 可重组合的母函数为()x G ＝∏∑==⎪⎪⎭⎫ ⎝⎛mi n j ji x 10＝∑=n r r r x a 0 (2.1.1) 其中，r 可重组合数为rx 之系数r a ，r ＝0,1,2, …,n .定理2.1.1的最大优点在于：● 将无重组合与重复组合统一起来处理；● 使处理可重组合的枚举问题变得非常简单。

习题二（母函数及其应用）1．求下列数列的母函数(0,1,2,)n =（1）(1)n a n ⎧⎫⎛⎫-⎨⎬ ⎪⎝⎭⎩⎭；（2）{5}n +； （3）{(1)}n n -； （4）{(2)}n n +；解：（1）母函数为：00()(1)()(1)nn n a n n a a G x x x x n n ∞∞==⎛⎫⎛⎫=-=-=- ⎪ ⎪⎝⎭⎝⎭∑∑；（2）母函数为：22554()(5)5(1)1(1)nnn n n n x xG x n x nx x x x x ∞∞∞===-=+=+=+=---∑∑∑； ♦ 方法二：()()()001022()(5)14414111114541(1)1nnnn n n n n G x n x n x x x x x x x x x x ∞∞∞===∞+==+=++''⎛⎫=+=-+⎪---⎝⎭-=+=---∑∑∑∑ （3）母函数为：2323000222()(1)(1)2(1)(1)(1)nnnn n n x x x G x n n x n n x nx x x x ∞∞∞====-=+-=-=---∑∑∑； ♦ 方法二：()()()()()2202222002222023()(1)00121121nn n n nn n n n n G x n n x xn n xxn n x xx x x x x x x x ∞∞-==∞∞+==∞+==-=++-"=++=""⎛⎫⎛⎫== ⎪⎪-⎝⎭⎝⎭=-∑∑∑∑∑（4）母函数为：232300023()(2)(1)(1)(1)(1)nnnn n n x x x x G x n n x n n x nx x x x ∞∞∞===-=+=++=+=---∑∑∑。

♦ 方法二：()()()()()()()()00212100023223()(2)1211111121111111131nnnnn n n n n n n n n n n n G x n n x n n x n x x x x x x x xx x x x x x x x x x x ∞∞∞∞====∞∞∞∞++++=====+=++-+-"'"'⎛⎫⎛⎫=--=-- ⎪ ⎪--⎝⎭⎝⎭"'⎛⎫⎛⎫=--=-- ⎪ ⎪----⎝⎭--⎝⎭-=-∑∑∑∑∑∑∑∑2．证明序列(,),(1,),(2,),C n n C n n C n n ++ 的母函数为 11(1)n x +- 。

习题四（容斥原理）1．试求不超过200的正整数中素数的个数。

解：因为2215225,13169==，所以不超过200的合数必是2,3,5,7,11,13的倍数，而且其因子又不可能都超过13。

设i A 为数i 不超过200的倍数集，2,3,5,7,11,13i =，则22001002A ⎢⎥==⎢⎥⎣⎦，3200663A ⎢⎥==⎢⎥⎣⎦，5200405A ⎢⎥==⎢⎥⎣⎦，7200287A ⎢⎥==⎢⎥⎣⎦， 112001811A ⎢⎥==⎢⎥⎣⎦，132001513A ⎢⎥==⎢⎥⎣⎦，232003323A A ⎢⎥==⎢⎥⨯⎣⎦， 252002025A A ⎢⎥==⎢⎥⨯⎣⎦，272001427A A ⎢⎥==⎢⎥⨯⎣⎦，2112009211A A ⎢⎥==⎢⎥⨯⎣⎦， 2132007213A A ⎢⎥==⎢⎥⨯⎣⎦，352001335A A ⎢⎥==⎢⎥⨯⎣⎦，37200937A A ⎢⎥==⎢⎥⨯⎣⎦， 3112006311A A ⎢⎥==⎢⎥⨯⎣⎦，3132005313A A ⎢⎥==⎢⎥⨯⎣⎦，57200557A A ⎢⎥==⎢⎥⨯⎣⎦， 5112003511A A ⎢⎥==⎢⎥⨯⎣⎦，5132003513A A ⎢⎥==⎢⎥⨯⎣⎦，7112002711A A ⎢⎥==⎢⎥⨯⎣⎦， 7132002713A A ⎢⎥==⎢⎥⨯⎣⎦，111320011113A A ⎢⎥==⎢⎥⨯⎣⎦，2352006235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 2372004237A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231120032311A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231320022313A A A ⎢⎥==⎢⎥⨯⨯⎣⎦ 2572002257A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251120012511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251320012513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 271120012711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，271320012713A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 21113200021113A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，3572001357A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，351120013511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦351320013513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，371120003711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，…， 235720002357A A A A ⎢⎥==⎢⎥⨯⨯⨯⎣⎦，…，23571113200023571113A A A A A A ⎢⎥==⎢⎥⨯⨯⨯⨯⨯⎣⎦， 所以 23571113200(1006640281815)(3320149713965533221)(6432211110111i i j i j k i j k lii ji j ki j k li j k l m i j k l m ni j k l mi j k l m nA A A A A A S A A A A A A A A A A A A A A A A A A A A A <<<<<<<<<<<<<<<=-+-+-+=-++++++++++++++++++++-+++++++++++++∑∑∑∑∑∑0)00041+-+=但这41个数未包括2,3,5,7,11,13本身，却将非素数1包含其中， 故所求的素数个数为：416146+-=2．问由1到2000的整数中：（1）至少能被2，3，5之一整除的数有多少个？ （2）至少能被2，3，5中2个数同时整除的数有多少个？ （3）能且只能被2，3，5中1个数整除的数有多少个？ 解：设i A 为1到2000的整数中能被i 整除的数的集合，2,3,5i =，则2200010002A ⎢⎥==⎢⎥⎣⎦，320006663A ⎢⎥==⎢⎥⎣⎦，520004005A ⎢⎥==⎢⎥⎣⎦， 23200033323A A ⎢⎥==⎢⎥⨯⎣⎦，25200020025A A ⎢⎥==⎢⎥⨯⎣⎦，35200013335A A ⎢⎥==⎢⎥⨯⎣⎦， 235200066235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， （1）即求235A A A ++，根据容斥原理有：235235232535235()1000666400(333200133)661466A A A A A A A A A A A A A A A ++=++-+++=++-+++=（2）即求232535A A A A A A ++，根据容斥原理有：232535232535235235235235()333200133266534A A A A A A A A A A A A A A A A A A A A A A A A ++=++-+++=++-⨯=（3）即求[1]N ，根据Jordan 公式有：1112233235232535235[1]2()310006664002(333200133)366932N q C q C q A A A A A A A A A A A A =-+=++-⨯+++⨯=++-⨯+++⨯=3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。

第二章母函数及其应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法新方法：母函数方法。

基本思想：把离散的数列同多项式或幂级数一一对应起来，算。

2.1 母函数（一）母函数（1）定义【定义2.1.1】对于数列{}n a ，称无穷级数()∑∞=≡0n n n x a x G 为该数列的（普通型）母函数，简称普母函数或母函数。

（2）例【例2.1.1】有限数列rn C （r ＝0, 1, 2, …, n ）的普母函数：()x G ＝nn n n n nx C x C x C C ++++ 2210＝()nx +1【例2.1.2】无限数列{1, 1. …, 1, …}的普母函数：()x G ＝ +++++nx x x 21＝x-11（3）说明● n a 可以为有限个或无限个。

● 数列{}n a 与母函数一一对应。

{0, 1, 1, …, 1, …}↔ +++++n x x x 20＝xx -1 ● 将母函数视为形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”。

（4）常用母函数（二） 组合问题 （1）组合的母函数【定理2.1.1】组合的母函数：设{}m m e n e n e n S ⋅⋅⋅=,,,2211 ,且n 1＋n 2＋…＋n m ＝n ，则S 的r 可重组合的母函数为()x G ＝∏∑==⎪⎪⎭⎫ ⎝⎛mi n j j i x 10＝∑=n r r r x a 0其中，r 可重组合数为rx 之系数r a ，r ＝0, 1, 2, …, n 。

理论依据：多项式的任何一项与组合结果一一对应。

【例2.1.3】设有6个红球，7个黑球，8个白球，问 （1） 共有多少种不同的选取方法，试加以枚举？ （2） 若每次从中任取3个，有多少种不同的取法？ （解）（1）元素符号化（x ，y ，z ↔红、黑、白球），元素的个数以符号的指数区分。

母函数G (x , y , z ) ＝(1＋x ＋x 2) (1＋y ) (1＋z )＝1＋(x ＋y ＋z )＋(x 2＋xy ＋xz ＋yz )＋(x 2x ＋x 2x ＋xxx )＋( x 2yz )5种情况：① 数字1表示一个球也不取的情况，共有1种方案； ② 取1个球的方案有3种，即红、黑、白三种球只取1个； ③ 取2个球的方案有4种，即2红、1红1黑、1红1白、1黑1白； ④ 取3个球的方案有3种，即2红1黑、2红1白、三色球各一； ⑤ 取4个球的方案有1种，即全取。

《组合数学》课程教学大纲课程名称：组合数学英文名称：Combinatorial Mathematics 课程代码: ZS1051001课程类别: 专业选修学分: 3 学时: 48开课单位: 理学院适用专业: 数学与应用数学（师范教育方向）制订人：审核人：审定人:一、课程性质与目的（一）课程的性质组合数学是高等师范院校数学与应用数学专业的专业选修课。

组合数学起源于古代的数学游戏和美学消遣，它以无穷的魅力激发人们的聪明才智和数学兴趣。

组合数学的离散性及其算法与计算机的结合已在现代科学技术中发挥出极为重要的作用。

它的一个重要组成部分——试验设计有着重大的应用价值，它的数学原理就是组合设计。

用组合设计的方法解决实际应用中的试验设计问题在西方发达国家已经得到了广泛的重视，并投入了大量的人力物力进行相关的研究与产品的开发。

所以说，组合数学是一门提高思维分析能力和自我构造算法本领的课程。

（二）课程的目的通过本课程的学习要求学生理解组合数学的基本概念与基本原理，掌握组合理论的基本方法和技巧，提高学生综合应用排列与组合、代数与编码、优化与规划的能力，为深入研究组合数学打好基础。

二、与相关课程的联系与分工本课程是数学与应用数学专业的专业选修课，它以数学分析、高等代数、概率论为基础，培养学生逻辑推理能力，科学计算能力，解决实际问题的能力，对离散问题的分析能力，为编程与编码作准备。

组合数学不仅在计算机软件科学技术中有着重要的应用价值，在企业管理，交通规划，战争指挥，金融分析，电子工程、数字通讯等诸多领域中也具有广泛而重要的应用。

三、教学内容及要求第一章排列与组合【教学要求】掌握加法法则与乘法法则，会利用排列与组合解决具体的实际问题。

【教学重点】加法法则与乘法法则；一一对应；排列与组合；组合意义的灵活运用；【教学难点】排列的生成算法；允许重复的组合与不相邻的组合；【教学内容】第一节加法法则与乘法法则第二节一一对应第三节排列与组合一、排列与组合的模型二、排列与组合问题的举例第四节圆周排列第五节排列的生成算法一、序数法二、字典序法三、换位法第六节允许重复的组合与不相邻的组合一、允许重复的组合二、不相邻的组合三、线性方程的整数解的个数问题四、组合的生成第七节组合意义的解释第八节应用举例第九节Stirling公式*一、Wallis公式*二、Stirling公式的证明第二章递推关系与母函数【教学要求】会利用递推关系与母函数解决实际问题。