3.1母函数与基本组合计数问题2014

《3.1母函数与基本组合计数问题2014》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合论第三章母函数(GeneratingFunction)1概述母函数起源母函数也叫生成函数,诞生于18世纪。1730年,deMoivre用母函数方法讨论了Fibonacci数；十年后,Euler用母函数方法研究了正整数的分拆；但直到1812年,在Laplace的经典名著《概率的解析理论》中母函数才得到充分的应用,系统的发展。21概述母函数方法的基本思想是将要研究的离散数列转化成一个幂级数,然后用幂级数的代数运算或分析运算得出数列的有关性质，从而达到研究数列的目的.给定一数列{ak:k≥0}=a0,a1,

2、a2,…,称幂级数g(x)=a0+a1x+a2x2+…=∑k≥0akxk为数列{ak:k≥0}的母函数(普通型母函数)或生成函数.3概述母函数是组合论中求解计数问题的重要工具求有限制条件的组合个数求有限制条件的排列个数研究分拆数研究某些特殊数的性质解递推关系证明某些组合恒等式广泛应用于数论、概率论、密码学等领域42概述知识点：形式幂级数两类母函数内容及掌握程度理解母函数概念熟练掌握母函数性质熟练掌握两类母函数的应用5组合论第三章母函数§3.1母函数与基本组合计数问题63本讲内容一、母函数与

3、不定方程的解二、母函数与基本组合计数7一、母函数与不定方程的解例1：给定正整数n，二项式系数的数列nnn:k0,,,0,0,kn0其母函数是nkngx()x(1x)k0k84定理3.1设pi和qi是非负整数,i=1,2,…,n,ak是不定方程x1+x2+…+xn=k,适合pi≤xi≤qi的整数解的个数.则数列{ak:k≥0}的母函数是gx=x+x()(p1p1+1++xq1)(x+xp2p2+1++xq2)()x+xpnpn+1++

4、xqn证我们只需证g(x)的展开式中xk的系数是ak即可.事实上g(x)的展开式中每一项形如xxmm12xmn故g(x)展开式中xk的系数即是不定方程x1+x2+…+xn=k,pi≤xi≤qi的整数解的个数ak.9例2n元集S={a1,a2,…,an}的k元重集的个数bk是不定方程x1+x2+…+xn=k的非负整数解的个数。则数列{bk:k≥0}的母函数是222Bx()(1xx)(1xx)(1xx)2n(1xx)证在定理3.1中令pi=0,qi→∞,i=1,2,…,k.可用

5、与定理3.1相同的方法证明，数列{bk:k≥0}的母函数是B(x).105222Bx()(1xx)(1xx)(1xx)2n(1xx)=(1–x)–n.由牛顿二项式定理，B(x)=(1–x)–n的展开式中xk的系数是(–1)kC(–n,k)=C(n+k–1,k).11定理3.2设Mi(1≤i≤n)是一些非负整数的集合,ck是不定方程x1+x2+…+xn=k满足xiMi的整数解的个数.则数列{ck:k≥0}的母函数为nkmgx=()cx=kx.k0i=1mM

6、i证g(x)(右端)展开式中每一项形如xm1xm2…xmn,其中xmi是g(x)的第i个因子中的一项.故g(x)(右端)展开式中xk的系数即是不定方程x1+x2+…+xn=k满足miMi的整数解的个数ck.126本讲内容一、母函数与不定方程的解二、母函数与基本组合计数13启示►单独求某个组合问题的计数有时比较困难或复杂.►我们知道组合计数问题的计数结果可表示成数列，若从整体上来考虑，利用多项式函数来进行研究有可能变得简单.147启示将组合计数问题的计数结果表示成数列{a:k0}{,,aaa,,a,}kk0

7、12对应幂级数k2gx=()axka0axax12k0称为该数列的母函数（普通型母函数）.15定理3.3从n元重集S={∞·a1,∞·a2,…,∞·an}中取k个元的组合,其中ai出现的次数限定集合为Mi(1≤i≤n),把这种组合的个数记为ck，则数列{ck:k≥0}的(普通型)母函数为：nkmcxkxk01imMi证因为nmkxx1i10mMinkm12mmkmiiM168例3求从n元重集S={∞·a1,∞·a

8、2,…,∞·an}取k个元的组合,规定每个元xi都至少出现一次的组合个数。分析：集合S={x1,x2,…,xn}xi的出现次数的限定集合Mi={1,2,…}解：设所求组合个数为ck，则该数列母函数为nkmcxkxk0i1m117nkmcxkxk0i1m12nn-n=(x+x+)=x(1-)xn+j-1