第7章_生成函数

1、 又称母函数或发生函数，可求解组合计数问题。又称母函数或发生函数，可求解组合计数问题。 在在求解递推关系求解递推关系的解、的解、整数分拆整数分拆以及以及证明组合恒等式证明组合恒等式时，时，生成函数是组合数学中的基本而重要的手段和方法，它是连接生成函数是组合数学中的基本而重要的手段和方法，它是连接离散数学与连续数学的桥梁，组合数学中的问题能借助于生成离散数学与连续数学的桥梁，组合数学中的问题能借助于生成函数的方法、原理，获得统一的处理和解决方式。函数的方法、原理，获得统一的处理和解决方式。 生成函数方法的基本思想是把生成函数方法的基本思想是把离散的数列离散的数列同同多项式或幂级多项式或幂级数数一

2、一对应起来，从而把离散数列间的组合关系转换为多项式一一对应起来，从而把离散数列间的组合关系转换为多项式或幂级数之间的运算。或幂级数之间的运算。7.1 .1 引论i=20j=0i=14j=1i=8j=2i=2j=37.1.2 形式幂级数xxRxR7.1.3生成函数的性质积分满足结合律积分满足结合律证明: xxGkk1110(1)(1) (2)(2) (3)(3) axaxxaaGkkkkkk11)(00111121 1(1)kkkkkkG kkxxkxxxxxxx牛顿二项式定理牛顿二项式定理1( 1) 1kGxk=0?(4)(4) 设设 1( ) (1)(1)kkA xG k kk kx则则 1

3、 0 0 0 01111211( )(1)(1)(1)xxxxkkkkkkkkkkA t dtk kt dtk kt dtktdtxkxxkxxx所以所以 22)1 ()(xxxA3)1 (2xx(5)(5) 122kkxkkG11) 1(kkkkkxkxk23)1 ()1 (2xxxx3)1 ()1 (xxx2 (1)xG kx2aa bb abb(6)(6) 设设 则则 所以所以 )()2)(1(xAkkkG 12 0 0 011222311( )(1)(2)(1)2(1)(1)(1)xxxkkkkkkkktA t dtk kktdtk ktdtxk kxxk kxxx323426( )(

4、1)(1)xxxA xxx故故 4)1 (6)(xxxA32 (1)(1)xG k kx(7)(7) xkkexkkG0!1!1(8)(8) 即二项式展开式即二项式展开式, )1 (0 xxkkGkk既可以将其看作定义，也可以利用既可以将其看作定义，也可以利用x=0的的指数函数的指数函数的Taylor展开式证明此结果。展开式证明此结果。(9)(9) 前面学到的牛顿二项式定理知前面学到的牛顿二项式定理知, ,有有 kknnxkknxx01)1 (1)1 (故故 10)1 (1nkkxxkknkknG用用n+1替换替换n1( 1) 1nGx11nG aaxk=n-1k=n-27.2 组合型分配问题

5、的生成函数选取的元素个数为选取的元素个数为k任意的整数集合任意的整数集合连续的整数区间连续的整数区间7.2.2组合型分配问题的生成函数组合型分配问题的生成函数任意的整数集合任意的整数集合n=10n=6n=0二项式定理二项式定理利用推论利用推论5.3.11( )()imjj PiG xx将将y2看作看作一个变量一个变量r=1512,. ( ),krrSeeeSraaA y 例:设求 的每个元素只出现偶数次的组合数解:令的生成函数是则224242201( )(1)(1)11121kknnnA yyyykknkyyynknyn 所以有12 ,(0,1,)021.rknrnannrn用生成函数的方法也

6、可以求解不定方程的整数解的个数。例: 求方程x1+x2+x3=1的整数解的个数，其中123,5.x x x 1122334,4,4,xxxxxx解做变换令则原方程变成12312313,0.xxxx x x 这个方程与原方程的解的个数相等。设解的个数为a13，则ar的生成函数是30013 12( ),22(1)rrrrrrA yyyy 所以有13132105.2a5.5 排列数的指数型生成函数排列数的指数型生成函数5.5 .1 排列数的指数型生成函数排列数的指数型生成函数:().(1)(,),0,1,.(2)1,0,1,.(3),0,1,.nennnnafxaP m nnanabn例设是 数 列

7、 求 它 的 指 数 生 成 函 数!00000(1)()(,)(,)(1).( 2 )()1.!()(3 )().!nennmnmnnxennnnb xennfxPmnCmnxxxfxenxb xfxbenn解00000.,( )( ),( )( ),!( ).( )( )!,!nneeneennnnkkn kknneenklklklabAxBxxAxBxCnCa bxGAxBxnxxabkl下面简单地介绍指数生成函数的性质及应用设的指数生成函数分别为和则其中证明000! ()!1!()!1( ),!nnkn kknkn kknnkkn kkCabnknkna bnknka bn比较上式两边比较上式两边xn的系数得的系数得0( ).nnnkkn kkCa b所以比较两个定理比较两个定理5.6 5.6 正整数的分拆正整数的分拆5.6.1 5.6.1 有序分拆有序分拆5.6.2 5.6.2 无序分拆无序分拆例如，例如，B(9,5)=5, 9 的所有的所有 5 分拆为：分拆为： 9 = 5 + 1 + 1 + 1+ 1 = 1 5 + 4 1 = 4 + 2 + 1 + 1+ 1 = 1 4 + 1 2 + 3 1 = 3 + 3 + 1 + 1 + 1 = 2 3 + 3 1