组合数学第二章1母函数

2.1母函数母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著—概率解析理论。两个色子掷出6点，有多少种选法？我们来看如下的例子方法的引入我们也可以从另一角度来看，要使两个色子掷出6点，第一个色子除了6以外的都可选，这有5种选法，一旦第一个选定，第二个色子就只有一种可能的选法按乘法法则有5*1=5种注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，这些选法互斥且穷尽了出现6点的一切可能的选法，按加法法则，共有2+2+1=5种不同选法。但碰到用三个或四个色子掷出n点，上述两方法就不胜其烦了。——这就需要引进新的方法。6261,2,...,6tt,(tt...t)t设想把色子的出现的点数和到对应起来则第一个色子可能出现的点数就与中的各次幂一一对应。262623456(tt...t)(tt...t)t2t3t4t5t....156246336516426ttt,ttt,ttt,ttt,ttt若有两个色子，则65中的t的系数显然相当于6诸乘积都产生t这一项的方案数66即，掷出点的方法组合成t的乘幂方法这种对应把组合问题的加法法则和幂级数的t的乘幂的相加对应起来。2626f(t)(tt...t)中t的系数f(t)--母函数26tt...t枚举子故使两个色子掷出6点的方法数等价于求母函数的思想很简单—即:把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造.122121213112(1)(1)(1)1()()(2-1-1)nnnnnnaxaxaxaaaxaaaaaaxaaax看下面的例子.2.1母函数中所有的项包括n个元素a1，a2，…an中取两个组合的全体；同理x3项系数包含了从n个元素a1，a2，…an中取3个元素组合全体。以此类推。212131nnxaaaaaa项的系数若令a1=a2=…=an=1，在（2-1-1）式2xnnaaaaaa13121项系数中每一个组合有1个贡献,其他各项以此类推.2.1母函数2)-1-(2),()2,()1,(1)1(2nnxnnCxnCxnCx故有：另一方面：nmnmxxx)1()1()1(nmmn[C(n,0)C(n,1)xC(n,n)x][C(m,0)C(m,1)xC(m,m)x]C(mn,0)C(mn,1)xC(mn,mn)x比较等号两端项对应系数，可得一等式)0,(),()1,()1,(),()0,(),(nCrmCrnCmCrnCmCrnmC2.1母函数用类似的方法可得等式：3)-1-(2)0,()0,()0,()0,()0,()0,(),(mCnCmCnCmCnCmnmCnmmmnxxxx)1()/11()1(证法如下：nm(1x)(11/x),mn同样对于（设）比较等式两端的常数项，即得公式(2-1-3)nmmmnxnmnmCxnmCxnmCnmCxxmmCxmCmCxnnCxnCnC),()2,()1,()0,([]),()1,()0,([]),()1,()0,([21又如等式：2(1)(,0)(,1)(,2)(,)nnxCnCnxCnxCnnx令x=1可得4)-1-(22),()2,()1,()0,(nnnCnCnCnC(2-1-2)式等号的两端对x求导可得：2n1n1C(n,1)2C(n,2)x3C(n,3)xnC(n,n)xn(1x)(2-1-5)等式(2-1-5)两端令x=1，得：1(,1)2(,2)3(,3)(,)2(2-1-6)nCnCnCnnCnnn2.1母函数用类似的方法还可以得到：132)1(),()3,(3)2,(2)1,(nnxnxxnnnCxnCxnCxnC7)-1-(22)1(),()3,(3)2,(2)1,(2222nnnnnCnnCnCnC2.1母函数已可见函数),(,),1,(),0,(nnCnCnC2012(),Gxaaxax还可以类似地推出一些等式，但通过上面一些例子的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：nx)1(在研究序列,,,210aaa称函数G(x)是序列的母函数,,,,210aaa定义：对于序列构造一函数。2.1母函数,(1)(,0),(,1),,(,)nxCnCnCnn例如是序列的母函数如若已知序列则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。,,,,210aaa,,,,210aaa}{na序列可记为2.2母函数的性质一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，特别酷似离散序列的Z变换。如前的例子所示的那样，为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。最后求逆变换，即从已求得的母函数G(x)得到序列{an}。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。这一节便是以此为目的的。)(xA)(xB对应的母函数分别为、}{ka}{kb不特别说明,下面假设、两个序列2.2母函数的性质2.2母函数的性质iikiikxbxBbxaxAa)(}{)(}{的母函数为序列的母函数为记序列,...2,1,)()()(ibaiffxBxAaii,.....3,2,1,0,......)()()(2210ibacxcxccxBxAbiii则若性质1:证:)(000)(11011xAxxaxaxbxbxBlllllllkblk0lkalk{)()(xAxxBl若则2.2母函数的性质例.已知1!3!2!132xexxxxA则)1(!3!2!1)(121xmmmmexxxxxB2.2母函数的性质性质2:则llkkkxxaxAxB/])([)(10lkkab若2.2母函数的性质llkkklllllllllllllxxaxAxxaxaxaaxAxaxaxaxxaxaaxB/])([/])([)(1)(101122102211221证：2210)(xbxbbxB2.2母函数的性质例.!5!3sin)(53xxxxxA6533/]!51!31[sin!91!71)(xxxxxxxxB2.2母函数的性质性质3：0kkiiba若xxAxB1)()(则2.2母函数的性质____________________________)1/()()1/(][)1/()1/()1/()(22102210xxAxxaxaaxxaxxaxaxB)::::12102102210100nnaaaabnxaaabxaabxab2.2母函数的性质证：例.已知xxxxxAn111)(2232)1(14321)(xxxxxB20)1(1)1(xxkkk2.2母函数的性质类似可得：232323k3k0C(x)(12x3x4x)(1xxx)13x6x10x11(k1)(k2)x2(1x)2.2母函数的性质0,kkjkjkaba若收敛性质4xxxAAxB1)()1()(则2.2母函数的性质)00121120222011:(1):(1):(1)baaaAxbaaAaxbaAaa____________________________)1()1(]1)[1()(221202xxxaxxxaxxAxB证2.2母函数的性质xxxAAxxxaaxAxB1)()1()1/()(1)1()(102.2母函数的性质例xxxxA111223211132xxxxxxx则性质5kkkabxxAxB'若则2.2母函数的性质性质5和性质6的结论是显而易见的。性质6kabkk1xdxxAxxB01若则2.2母函数的性质性质7022110babababackkkkkkiikiba0若xBxAxcxccxC2210则2.2母函数的性质证:22100xbxbbaxC22101xbxbbxa221022xbxbbxa22102210xbxbbxaxaaxBxAxC)0001:,cab10110:,xcabab22021120:,xcababab______________________2.2母函数的性质,21321,132,1112322kkkCxxxxxxBxxxxAk已知例.31xxxC则2.2母函数的性质所谓正整数拆分即把正整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。2.3整数的拆分--2.3.1问题描述2.3.2问题举例例1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？234233472345678910(1x)(1x)(1x)(1x)(1xxx)(1xxx)1xx2x2x2x2x2xxxx从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有项，即称出5克的方案有252x41325同样，432110243216故称出6克的方案有2，称出10克的方案有12.3.2问题举例例2：求用1分、2分、3分的邮票贴出不同数值的方案数。解:因邮票允许重复，故母函数为)1()1)(1()(63422xxxxxxxG2231211111142.3.2问题举例以其中x为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即4例3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？2.3.2问题举例23246848()(1)(1)(1)Gxxxxxxxxxx解:作目函数234567891011482345678910111213141516171819(122222222)(1)12233445555443322xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx2.3.2问题举例2.3.2问题举例1211224N,,......01,1,2,...nnniaaaaxaxaxNxin例，将无序剖分成正整数，且不允许重复。这个问题对应于不定方程的整数解问题。122,()(1)(1)...(1)(a