第四章母函数及应用

第四章母函数及应用§4.1母函数的基本概念----母函数是序列的一种表示,它又称为发生函数或生成函数,是解决组合计数问题的有效工具之一常见母函数:1.普通母函数----适用于包含组合数的序列定义4.1.1

给定无穷序列{a0,a1,a2,…,an,…},简记为{an},称函数为序列{a0,a1,a2,…,an,…}的普通母函数.注:①普通母函数从形式上看是一个无穷级数,但没有必要讨论它的收敛性,它实质上是序列的记号,x为形式变元.对该级数可把它看成形式幂级数,从而可进行加法、乘法及形式微分等运算,从而构成一个代数体系。②一个序列和它的普通母函数是一一对应的。③对有限序列{a0,a1,a2,…,an},它可表示为无穷序列{a0,a1,a2,…,an,…},，其中an+1=an+2=…=0。例1

序列普通母函数为。例2

序列普通母函数为。

序列普通母函数为

例3

求序列普通母函数。2.指数母函数----适用于包含排列数的序列定义4.1.2

给定无穷序列{a0,a1,a2,…,an,…},称函数为序列{a0,a1,a2,…,an,…}的指数母函数.例3①序列{P(n,0),P(n,1),…,P(n,n)}的指数母函数为②序列{P(0,0),P(2,1),…,P(2n,n),…}的指数母函数为

普通母函数与指数母函数间的关系：设f(x)，fe(x)分别为序列{a0,a1,a2,…,an,…}的普通母函数和指数母函数，则§4.2母函数的运算1.普通母函数设A(x),B(x),C(x)分别为序列{a0,a1,a2,…,an,…},{b0,b1,b2,…,bn,…},{c0,c1,c2,…,cn,…}的普通母函数，则有以下定义⑴C(x)=A(x)+B(x)当且仅当ci=ai+bi,i=0,1,…,n,…;

⑵

C(x)=A(x)B(x)当且仅当例1

设A(x)为序列{a0,a1,…,an,…}的普通母函数,则A(x)/(1-x)为序列{a0,a0+a1,…,a0+a1+…+an,…}的普通母函数。例2

求和的值。2.指数母函数设A(x),B(x),C(x)分别为序列{a0,a1,a2,…,an,…},{b0,b1,b2,…,bn,…},{c0,c1,c2,…,cn,…}的指数母函数，则有以下定义⑴C(x)=A(x)+B(x)当且仅当ci=ai+bi,i=0,1,…,n,…;

⑵

C(x)=A(x)B(x)当且仅当，

i=0,1,…,n,…;例4

证明下列恒等式：普通母函数的基本性质1)若则.2)若,则

3)若则

4)若收敛,,则

5)若,则

6)若,则.§4.3母函数在排列、组合中的应用一、考虑从n个不同物体中选取k个的方式数表示⑴三个不同的物体a、b、c，从中选取一个：或选a，或选b，或选c，这些可能的选取象征性地记为

a+b+c.

从a、b、c中选取两个有三种方法：或选a与b，或选b与c，或选c与a，这些可能的选取也可象征性地记为

ab+bc+ca.从a、b、c中选取三个只有一种方法，象征性地记为abc。再考虑以下多项式(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+abcx3从中可见，以上所有可能的选取可作为x幂的系数被表示出来，即xi的系数为从三个不同物体取i个物体的方式数。如只考虑选取方法的个数，则可令a=b=c=1即有

这样，有一种方法从三个物体中一个也不取，有3种方法从中取一个，有3种方法取2个，有一种方法取3个。

⑵由于故从n个不同物体中取k个的方法数即为xk的系数。⑶从n个不同物体中允许重复选取k个物体1+x：可象征地表示一物体可不选，或只选取一次，即至多选取一次；

1+x+x2:可象征地表示一物体可不选，或只选取一次，或选取两次，即至多选取两次；1+x+x2+x3+….：可象征地表示一物体可不选，或只选取一次，或选取两次，或选取三次，….。这样，中xk的系数即可表示从n个不同物体中允许重复取k个物体的方式数。二、普通母函数在组合计数问题中的应用例1

求⑴从n个不同物体中允许重复选取k个不同的物体的方式数为F(n,k)；⑵从n个不同物体中允许重复选取k个不同的物体，但每个物体至少出现一次的方式数；⑶从n个不同物体中允许重复选取k个不同的物体，但每个物体至少出现奇数次的方式数；⑷从n个不同物体中允许重复选取2k个不同的物体，但每个物体至少出现偶数次的方式数；例2

一个书架上共有16本书，其中4本高等数学，3本普通物理，4本数据结构，5本离散数学，⑴求从中选取k本书的方式数，其中k=12；⑵k=12本书中至少有2本高数，1本物理，又有多少种选取方式？例3

现有无穷多个字母A、B、C，求从中取n个字母但必须含有偶数个A的方式数。例4

现有2n个A，2n个B和2n个C，求从它们中选取3n个字母的不同方式数。三、指数母函数在排列计数问题中的应用已知所以从n个不同物体中取k个物体的组合数ak所成序列的普通母函数可变为此表明，从n个不同物体中取k的排列数所成序列的指数母函数为(1+x)n。另外，象征性地表示某一物体在排列中可以不取或取一次，同样某物体在排列中可以不取，或取一次，或取两次，….，或取k次可象征性地表示为如某物体的重复次数为无穷次，则上式为例1

求从n个不同物体中允许重复地选取r个物体的排列数(nr)。例2

求1,3,5,7,9五个数字组成的r位数的个数，其中要求7、9出现的次数为偶数，其他数字的出现不限。例3

求由数字2,3,4,5,6,7组成的r位数中，3和5出现偶数次，