下载文档原格式
母函数（生成函数）（发生函数）（发生函数）英文：generating function我们已知道了解决组合的计数问题的几种方法，从基本的加法原理和乘法原理开始，导出了排列与组合的各种公式，证明了容斥原理，并且已用它来解决某些计数问题。
这里将论证一种方法是属于Eular 的生成函数法。
（对工程师来说，数列的母函数通称为z-变换）§1 母函数利用生成函数可以说是研究计数问题的一个最主要的一般方法：其基本思想很简单：为了获得一个数列{} 210,,0:a a a k a k=≥的知识，我们用一个母函数+++=∑=≥22100)(x a x a a xa x g kk k这里x k 是指数函数来整体地表示这个数列，称g （x ）是数列{}0:kx a k 的普通母函数，这样原数列就转记为成函数。
假如能求得这个函数，则不仅原则上已确定了原数列，还可以通过对函数的运算和分析得到这个数列的许多性质。
这里如果把x k 提成)(x k μ亦称普通母函数指数函数通常选来使得没有两个不同的序列令产生同一个母函数，故序列的母函数仅只是序列的另一种表示。
如1，cos x ，cos2x ，…为指数函数，序列{}2,,1ωω的母函数为+++++=rx x x x F rcos 2cos cos1)(2ωωω另一方面，用，1，1+x ，1-x ，1+x 2，1-x 2，…，1+x r ，1-x r …作为指数函数，序列（3，2，6，0，0）的普通母函数是3+2（1+x ）+6（1-x ）=11-4x ，而序列（1，3，7，6，0）和（1，2，6，1，1）会产生同一母函数即，1+3（1+x ）+7（1-x ）=11-4x ，xx x x x 411)1()1()1(6)1(2122-=-+++-+++故函数 ,1,1,1,1,122x x x x -+-+不应做为指数函数，)(x r μ的最近常用的是r x ，以下我们仅讨论这种情况的指数函数。
母函数（⽣成函数）介绍母函数是组合数学中相当重要的⼀个知识点，可以⽤来解决⼀些排列组合问题，还有所有的常系数线性齐次递推问题。
如果系数不是常数，需要根据具体情况进⾏处理。
具体的内容可以看组合数学相关书籍或者，由于⼤佬总是想当然地把别⼈当成⼤佬，⼀些内容对（像我这种）蒟蒻来说不是很友好，在这⾥讲⼀下母函数的基础。
（研究母函数时，钦定|x|<1）,这样，由等⽐数列求和公式有：11−x=∑∞i=0x i=1+x+ (x)11−kx=∑∞i=0k i x i=1+kx+...+k∞x∞1.普通型母函数。
假设有⼀个数列a,那么它的母函数其实就是⼀个关于x的多项式，x n的系数为a n，对于已知通项的数列，其母函数可以直接写出来。
⽽对于未知的数列，主要分为两类：递推型和组合型。
递推型就是利⽤错位相消，举个栗⼦：a n=3a n−1+10a n−2,a0=1,a1=2移项，得a n−3a n−1−10a n−2=0，设a n的母函数为G(x)G(x)=a0+a1x+a2x2+a3x3...−3xG(x)=−3a0x+(−3)a1x2+(−3)a2x3...−10x2G(x)=−10a0x2+(−10)a1x3三⾏相加，可以发现等式右侧除了第⼀⾏的第1,2项和第⼆⾏的第1项外全消掉了。
所以我们可以得到(1−3x−10x2)G(x)=a0+a1x−3a0x=1−x，即G(x)=1−x1−3x−10x2，⽣成函数就求出来了，那如果我们还要求an的通项呢？对于这种东西，我们可以把他化成k1x−A+k2x−B这种形式，其中A和B由分母的因式分解唯⼀确定，然后k1,k2可由待定系数法解得。
然后对于kx−A,总可以化成k′∗11−Nx，就是k′∑∞i=0N i x i，找出x k的系数就是a n，如果母函数拆开成多个该类分式的话各部分相加就好。
具体计算就不算了。
PS:⼀部分⾮齐次线性递推其实也可以这样解，⽐如a n−3a n−1−10a n−2=f(n)，按照上述⽅法错项后会剩下⼀个等⽐数列和前⼏项余项。
六、母函数及其应用6．1定义：称() +++++=-12321n n x a x a x a a x f 为数列{}n a 的形式幂级数，或生成函数，简称母函数。
6．2几个常用初等函数的形式幂级数展开式（1）()111<=-∑+∞=x x x n n ；（2）()()()()1!1110<-+⋅⋅-⋅=+∑+∞=x x n n x n n αααα；（3）()R x n x e n nx∈=∑+∞=0!；（4）()()()R x n x x n nn∈-=∑+∞=02!21cos ； （5）()()()R x n x x n n n∈+-=∑+∞=+012!121sin ； （6）()()()111ln 01<-=+∑+∞=-x nx x n nn ； （7）()()1121arctan 012<+-=∑+∞=+x n x x n n n。
求一个初等函数的形式幂级数的根本方法是利用泰勒展开定理，或马克劳林定理。
在定义域范围内，对上述形式幂级数再进行算术运算和解析运算，可以得到其它初等函数的形式幂级数。
我们在下文的目的，就是利用这种运算方法来求数列的通项公式。
6．3数列{}n a 及其前n 项和数列{}n S 的母函数关系定理1：记数列{}n a 的母函数为()x A ，则其n 项和数列{}n S 的母函数()()xx A x B -=1。
证明：∵ ()()∑∑∑∑+∞=-+∞=-+∞=--+∞=-++=++==21111211111n n n n n n n n n n n n n x a xS x a xa S a xSx B()()()()x A x xB a x A x xB a +=-++=11∴ ()()xx A x B -=1。
定理2：()()*121N n n n k nk ∈+=∑=。
证明：记数列{}n 的前n 项和为n S ，则数列{}n S 的母函数为()()∑∑∑∑+∞=-+∞=-+∞=--+∞=-++=++==21112111111n n n n n n n n n n n nx xS x xn S S xS x B()()()()22111111x x xB x x xB -+=--++=∴ ()()()()∑∑∞+=-∞+=--=⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛-=-=22'11'2312121112111n n x n n x x n n nx x x x B ()∑+∞=-+=11121n n nx n 。
第二章 母函数及其应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法是比较麻烦的（参见表2.0.1）。
新方法：母函数方法，问题将显得容易多了。
其次，在求解递推关系的解、整数分拆以及证明组合恒等式时，母函数方法是一种非常重要的手段。
表2.0.1 条件组合方案数排列方案数对应的集合相异元素，不重复()!!!r n r n C rn -⋅=()!!r n n P rn -={}n e e e S ,,, 21=相异元素，可重复rr n C 1-+rnS ＝{,,21e e ⋅∞⋅∞ne ⋅∞, }不尽相异元素（有限重复）特例r ＝n1 !!!!m n n n n 21S ＝{11e n ⋅，22e n ⋅，…，m m e n ⋅}, n 1＋n 2＋…＋n m ＝nn k ≣1, (k ＝1,2,…, m )r ＝1mm所有n k ≣r rr m C 1-+rm至少有一个n k 满足1≢n k < r母函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转化为多项式或幂级数之间的运算。
2.1 母 函 数（一）母函数（1）定义定义2.1.1 对于数列{}n a ，称无穷级数()∑∞=≡0n nnxax G 为该数列的（普通型）母函数，简称普母函数或母函数。
（2）例例2.1.1 有限数列C (n ,r )，r ＝0,1,2, …,n 的普母函数是()nx +1。
例2.1.2 无限数列{1，1，…，1，…}的普母函数是+++++=-nxx x x2111（3）说明● n a 可以为有限个或无限个； ● 数列{}n a 与母函数一一对应，即给定数列便得知它的母函数；反之，求得母函数则数列也随之而定；例如，无限数列{0，1，1，…，1，…}的普母函数是 +++++n x x x 20＝xx-1● 这里将母函数只看作一个形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”，而且始终认为它是可“逐项微分”和“逐项积分”的。
母函数母函数思想的起源可以追溯到18世纪Jacob B的《猜度术》一书。
这本书是在作者去世8年后的1713年出版的，它是早期概率论中最重要的著作。
《猜度术》一书共分四个部分，其中在第二部分中，作者讨论了组合论问题。
主要是运用伯努利数通过完全归纳法证明了n 为正整数时的二项式定理。
在第三部分中，作者把排列和组合的理论运用到概率论中，给出了24种有关在各种赌博情形中利益预测的例子。
在第四部分中作者给出了著名的伯努利大数定律:若P是事件发生一次的概率，q是该事件不发生的概率，则在n次实验中该事件至少出现m次的概率等于的展开式中从项到包括为止的各项之和。
母函数是组合数学的一个重要理论。
Jacob B考虑掷n粒骰子时所得点数总和等于m，这种场合的数目等于的展开式中这一项的系数，开了母函数研究的先河。
在18世纪，Euler L对组合方法的发展做出了重大贡献。
他关于自然数的分解与合成的研究为母函数方法奠定了基础。
1812年，法国数学家Laplace P.S. 出版了《概率的分析理论》一书。
这本书第一部分的小标题为“母函数的计算”，这一部分致力于母函数计算的数学方法及其一般数学理论，这是对Euler L所提出的母函数理论的发展。
所以现代学术界认为母函数方法是由Euler L和Laplace P.S. 共同发现的。
由此，组合数学中的母函数理论基本建立起来了。
在当代组合学理论中，母函数是解决计数问题的重要方法。
一方面，母函数可以看成是代数对象，其形式上的处理使得人们可以通过代数手段计算一个问题的可能性的数目；另一个方面，母函数是无限可微分函数的Taylor级数。
如果能够找到函数和它的Talor级数，那么Taylor级数的系数则给出了问题的解。
本章主要介绍母函数的两种形式：普通型母函数和指数型母函数。
然后通过一些典型问题的分析，帮助读者加深对这一方法的理解。
并且在分析中，有的问题采用多种方法求解。
通过对比，读者可以明显地看到用母函数的方法解决问题具有较高的效率，并且程序具有非常规范的形式，易于实现。
母函数和特征函数简介§1 母函数（生成函数）简介对于取值非负整数的随机变量，其母函数有极其良好的性质且又便于计算和分析，因此引入母函数是非常必要的。
母函数又称生成函数(Generating function)。
母函数的定义● 定义：对于数列}0,{≥n a n ，称幂级数)1(0≤∑∞=s sa n nn 为}0,{≥n a n 的母函数。
● 定义：设X 为取值于非负整数随机变量，分布率为 ,2,1,0,}{===k p x X P k k ，则称1)(?)(0≤==∑∞=s s p s E s g k kk X为随机变量X 的概率母函数，简称母函数。
一些常用分布的母函数（1）若).(~p n B X ，则n sp q s g )()(+=（2）若)(~λPo X ，则)1()(-=s e s g λ （3）若)(~p G X ，则qs pss g -=1)(母函数的基本性质（1）X 的母函数与其分布率是一一对应的，且有!)0()(k g p k k =（2）设非负整值随机变量n X X X ,,,21 相互独立，而n g g g ,,,21 分别是它们的母函数，则∑==nk kXY 1的母函数为：)()()()(21s g s g s g s g n Y =（3）设随机变量X 的母函数为)(s g ，则有：（a ）)1()(g X E '=（b ）2)]1([)1()1()()(g g g X Var X D '-'+''==母函数的应用（4）设n X X X ,,,21 独立同分布，且).1(~p B X i ，求∑==nk kXY 1的分布。
（5）设21,X X 独立，且2,1,).(~=i p n B X i i ，证明),(~2121p n n B X X ++。
（6）设21,X X 独立，且2,1,)(~=i Po X i i λ，证明)(~2121λλ++Po X X 。
母函数
定义对给定序列构造一个函数，称为序列的母函数。
其中，序列只作为标志用，称为标志函数。
派生1：普通型母函数
当标志函数为时，即母函数为，称这类母函数为普通型母函数，可记作。
定理1：
设从元集合中取个元素组合，若限定元素出现次数的集合为，则该组合数序列的母函数为:
常用到的普通型母函数有：
例题：求位十进制正数中出现偶数个的数的个数
设表示位十进制正数中出现偶数个的数的个数，表示位十进制正数中出现奇数个的数的个数，不难得出：设序列，的母函数分别为：
由得：
再由得：
由、可得：
更进一步的，
即:
派生2：指数型母函数
当标志函数为时，即母函数为，称此类母函数为指数型母函数，可记作。
定理2：
从多重集中选区个元素排列，若元素出现的次数集合为，则该排列数序列的母函数为：
所谓多重集（multiset）之于集合（set），英文写出来差不多就懂了。
函数中，除以是因为排列中这个相同元素的先后是不考虑的。
常见的指数型母函数（的Tylor展开式）：
例题：求由这个数字组成的位数字的个数（每个数字出现次数可以为，且出现的次数为偶数）。
设满足条件的位数字的数目为（特别地，规定），则序列的母函数为：
故。
附录：
推荐的文档组合数学--母函数与递推朱全民。
