第四章 母函数及应用.ppt

第四章母函数及应用
§ 母函数的基本概念
----母函数是序列的一种表示,它又称为发生函数或生成函数,是解决组合计数问题的有效工具之一
常见母函数:
----适用于包含组合数的序列
给定无穷序列{a0,a1,a2,…,an,…},简记为{an},称函数
为序列{a0,a1,a2,…,an,…}的普通母函数.
注:
①普通母函数从形式上看是一个无穷级数,但没有必要讨论它的收敛性,它实质上是序列的记号,,从而可进行加法、乘法及形式微分等运算,从而构成一个代数体系。
②一个序列和它的普通母函数是一一对应的。
③对有限序列{a0,a1,a2,…,an}, 它可表示为无穷序列{a0,a1,a2,…,an,…},,其中an+1 =an+2 =…=0。
例1 序列普通母函数为。
例2 序列普通母函数为。

序列普通母函数为
例3 求序列
普通母函数。
----适用于包含排列数的序列
给定无穷序列{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,…}的普通母函数和指数母函数,则
§ 母函数的运算

设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 求和的值。

设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)若, 则.