组合数学课件(第七章-生成函数)

组合数学课件制作讲授：王继顺目录（1）第1章什么是组合数学1.1引例1.2组合数学研究对象、内容和方法第2章鸽巢原理2.1鸽巢原理：简单形式2.2鸽巢原理：加强形式2.3Ramsey定理2.4鸽巢原理与Ramsey定理的应用本章小结习题第3章排列与组合3.1两个基本的计数原理3.2集合的排列与组合3.3多重集的排列与组合本章小结习题第四章二项式系数4.1二项式定理4.2组合恒等式4.3非降路径问题4.4牛顿二项式定理4.5多项式定理4.6基本组合计数的应用本章小结习题第五章包含排斥原理5.1包含排斥原理5.2多重集的r-组合数5.3错位排列5.4有限制条件的排列问题5.5有禁区的排列问题本章小结习题目录目录（2）第六章递推关系6.1Fibonacci数列6.2常系数线性齐次递推关系的求解6.3常系数线性非齐次递推关系的求解6.4用迭代和归纳法求解递推关系本章小结习题第七章生成函数7.1生成函数的定义和性质7.2多重集的r-组合数7.3正整数的划分7.4指数生成函数与多重集的排列问题7.5Catalan数和Stiring数本章小结习题第八章Polya定理8.1置换群中的共轭类与轨道8.2Polya定理的特殊形式及其应用本章小结习题**********************课程总结第7章生成函数本章重点介绍生成函数（生成函数、指数生成函数）的基本概念及其在排列组合中的应用：•生成函数的基本概念•生成函数的基本运算•生成函数在排列、组合中的应用•整数拆分•生成函数在组合恒等式中的应用第7章生成函数•7.1生成函数的定义和性质•7.2多重集的r-组合数•7.3正整数的划分•7.4指数生成函数与多重集的排列问题•7.5Catalan数和Stiring第7章生成函数§7.1生成函数概念§4.1生成函数的基本概念定义4.14.1.1生成函数注：f(x)是无穷级数，不管其收敛性；x为形式变元，f(x)为形式幂级数；序列与生成函数一一对应；生成函数是序列的另一表达形式；有限序列也可用生成函数表示；可与二项式定理结合应用。给定一无穷序列(a0,a1,…an,…)(简记为{an})，称函数为序列{an}的生成函数（发生、普通母函数）。0()iiifxax§7.1生成函数例1§7.1生成函数的基本概念例题7.1.1生成函数例1、求序列(C(n,0),C(n,1),C(n,2),…,C(n,n))的生成函数。解：由定义7.1及二项式定理的推论有()...01(1)nnnnnfxxxnx§7.1生成函数例2§7.1生成函数的基本概念例题7.1.1生成函数例2、求序列(C(n-1,0),-C(n,1),C(n+1,2),…,(-1)kC(n+k-1,k),…)的生成函数。解：由定义7.1及二项式定理的推论3.10.2有200111()...(1)...0121(1)(1)kkkkkknknnnnkfxxxxknk=xkn=xxk§7.1生成函数例3§4.1生成函数的基本概念例题4.1.1生成函数例3、证明(1-4x)-1/2是序列(C(0,0),C(2,1),C(4,2),…,C(2n,n),…)的生成函数。证明：由牛顿二项式定理有由定义知，(1-4x)-1/2是序列(C(0,0),C(2,1),C(4,2),…,C(2n,n),…)的生成函数。12111112(14)1(4)12121122...1211(4)!413...(21)12!2!13...(21)1!!24...(2)13...(21kkkkkkkkkkkxxkk+xkk+xkkkxkkkk11121)!!(2)!211!!0242......012kkkkkkkxkkkkxxkkkkxxxk§7.1生成函数例4§7.1生成函数的基本概念例题7.1.1生成函数例4、求序列(0,1×2×3,2×3×4,…,n(n+1)(n+2),…)的生成函数。nnnnnnnnnxxnnxxnnnxxxxnnnxxxxnnnxxfxx023234340211.10.412(1)(1)6(1)(2)(1)6(1)(2)(1)0123234...(1)(2)...6()(1由牛顿二项式定理的推论，有将上式两端同时微分两次得将上式两端再微分得两边同乘解以得因此：nnn4(0123234,...,(1)(2),...))是序列，，的普通母函数。§7.1指数生成函数概念§7.1生成函数的基本概念定义7.27.1.2指数生成函数注：fe(x)也是形式幂函数。经常可结合以下公式运算：给定一无穷序列(a0,a1,…an,…)（简记为{an}），称函数为序列{an}的指数生成函数。ieiixfxai0()!nxnxxxen221......1!2!!nxnxxxen21...(1)...1!2!!nxxxxxeexn321sin......1!3!(21)!2§7.1指数生成函数例5§7.1生成函数的基本概念例题7.1.2指数生成函数例5、设n是整数，求序列(p(n,0),p(n,1),…,p(n,n))的指数生成函数fe(x)。解：由定义7.2及公式P(n,r)=r!C(n,r),以及例1的结论，有nennxxfxpnpnpnnnnnnxxnx()(,0)(,1)...(,)1!!...01(1)§7.1指数生成函数例6§7.1生成函数的基本概念例题7.1.2指数生成函数例6、求序列(p(0,0),p(2,1),p(4,2),…,p(2n,n),…)的指数生成函数fe(x)。解：由定义7.2及公式P(n,r)=r!C(n,r)，以及例3的结论，有nenxxxfxppppnnnnxxxnx2212()(0,0)(2,1)(4,2)...(2,)...1!2!!0242......012(14)§7.1指数生成函数例7§7.1生成函数的基本概念例题7.1.2指数生成函数例7、求序列{1,α,α2,…,αn,…}的指数生成函数fe(x)。其中α是实数。解：由定义7.2，有特别地：若=1，则序列(1,1,…,1,…)的指数生成函数为ex。nnxexxxfxen22()1......1!2!!§7.1指数生成函数例8§7.1生成函数的基本概念例题7.1.2指数生成函数例8、求序列(1,1×4,1×4×7,…,1×4×7×…×(3n+1),…)的指数生成函数。解：由定义7.2和二项式定理，有nennnnnnnnnxxxfxnnnxnnxnnxnxnx2011143()1(14)(147)...147...(31)...1!2!!147...(31)!3147...33313!4441...13331(3)!41(3)3(13)§7.1生成函数定理1§7.1生成函数的基本概念定理7.17.1.2指数生成函数设f(x)、fe(x)分别为序列{an}的普通、指数生成函数，则xefxefsxds0()()解：由指数生成函数的定义7.2，有将上式两边同乘以e-s并从0到积分得由分部积分法有故0()()!nennsxfsxan00000()!!nnnsssnennnnsxxefsxdseadsaesdsnn0!snesdsn00()()snennefsxdsaxfx设A(x),B(x),C(x)分别是序列{an},{bn}和{cn}的生成函数，则C(x)=A(x)+B(x)当且仅当ci=ai+bi,(i=0,1,…,r,…)C(x)=A(x)B(x)当且仅当,(i=0,1,…,r,…)§7.2生成函数运算定理2§7.2生成函数的基本运算定理7.2iikikkcab0§7.2生成函数运算例1§7.2生成函数的基本运算例题例1、设A(x)是序列{an}的生成函数，则A(x)/(1-x)是序列{a0,a0+a1,…,a0+a1+…+an,…}的生成函数。nnnnxxxxxBxxcaacaaaacaaaaaaAxxAxBxaaaaa20001010101010010111......1-1(1)(1,1,...,1,...)()1(1),111......11...1...()(1)()()(,,...,...由牛顿二项式定理知故是序列的普通母函数。令根据上述定理有故是明：序列证na,...)的普通母函数。§7.2生成函数运算例2§4.2生成函数的基本运算例题例2、求和的值。rii2022210203203222231(0,1,...,,...)(1-),1(1)1(1)1(0,1,...,,...)(1)111iiiiiirrirxxxxxxixxxxxxixxxxrxxcix先求序列的普通母函数。由牛顿二项式定理知将上式两端对微分再乘以得（）再将上式两端对微分再乘以得（）故（）是序列的普通母函数。故的普通母函数（）解为：244400421114131.102(1-)(1)1(2)(1)(1)(1)(1)(21)213!3!6(1)(21)6iiiirrrixxxxxiixxxiixxxxrrrrrrrrrrrrrrrrci（）（）由推论.知故的展开式中的系数为（）故§7.2生成函数运算推论1§7.2生成函数的基本运算六个推论推论7.2.1：0()()lkklklbBxxAxakl若，则0110111101111012012...0,,...,,...()......00...0...(...)()lllkklllllllllllbbbbababaBxbbxbxbxbxaxaxxaaxaxxAx证明：§7.2生成函数运算推论2§7.2生成函数的基本运算六个推论推论7.2.1：推论7.2.2：0()()lkklklbBxxAxakl若，则10()()lklkklkkbaBxAxaxx若，则20122121212121012110()......1...1()...1()llllllllllllllkklkBxbbxbxaaxaxaxaxaxxAxaaxaxaxxAxaxx证明：§7.2生成函数运算推论3§7.2生成函数的基本运算六个推论推论7.2.1：推论7.2.2：推论7.2.3：0()()lkklklbBxxAxakl若，则10()()lklkklkkbaBxAxaxx若，则0()()(1)kkiibaBxAxx若，则见本节例1。§7.2生成函数运算推论4§7.2生成函数的基本运算六个推论推论7.2.4：0()(1)()(1)kkjkjkabaBxAxAxx若收敛，，则20120012112022201()...1:...(1):...(1):...(1))....