第七章 组合数学 7.7生成函数 7.7.1幂级数型生成函数 定义1 生成函数 实数序列{an}的生成函数： 形式（不考虑收敛性）幂级数G(x)= a0x0+a1x1+a2x2+… 有限序列可以扩充为无限序列，得到生成函数 f(x)=akxk，g(x)=bkxk，则 (1) f(x)+g(x)=(ak+bk)xk (2) f(x)g(x)=0≤k<∞(0≤j≤kajbk-j)xk
例6 =1+x+x2+… = =0≤k<∞(k+1)xk = 常可用四则运算、求导、求积等求生成函数 定义1 推广的二项式系数 u任意实数，k任意整数
定理2 x<1，u实数，则 和 展开得： 用-x代替x得到
常用生成函数
（接上页图）
7.7.2幂级数型生成函数的应用例子 生成函数用于计数：本质上就是穷举法 例 2个苹果、3个橘子、2个香蕉，取4个有多少种取法？ f(x)=(1+x+x2)(1+x+x2+x3)(1+x+x2),展开后的x4的系数即为所求 例 有质量n1、n2、…、nk的砝码各一个。 （1）能称几种质量的物体？ （2）有几种称法？ f(x)= 例 有质量1、2、4、8、16的砝码各一个。 f(x)= = 1+x+x2+…+x31
例 有砝码1克2个、2克3个、5克2个。 （1）能称几种质量的物体？ （2）有几种称法？ f(x)=(1+x+x2)(1+x2+x4+x6)(1+x5+x10) 例 x1+x2+x3=7的整数解的数目。（1≤x1≤5，1≤x2≤3，0≤x3≤6） f(x)=(x+x2+…+x5)(x+x2+…+x3)(1+x+x2+…+x6) 例 A=n。 （1）A的可重复的r-组合数？ f(x)=(1+x+x2+…)n= （2）A的可重复的r-组合数，每个元素至少取一个？ （3）A的可重复的r-组合数，每个元素取偶数个？ f(x)=(1+x2+x4…)n= （4）A的可重复的r-组合数，每个元素取奇数个？
7.7.3指数型生成函数 7.7.4 用生成函数求解递推关系 例16 （P338） g(x)-3xg(x)=2，g(x)=2/(1-3x) 例17 （P338） 例 求Catalan数 7.7.5 用生成函数证明恒等式 例18 （P340）证明 (1+x)2n=(1+x)n(1+x)n