组合数学幻灯片41母函数的基本概念课件.ppt

1、 母函数又称发生函数或生成函数，它是解决计数问题的一个重要工具。母函数的类型较多，这里仅讨论最常见的两种类型的母函数：1.普通母函数 2.指数母函数下面，我们分别进行讨论。称函数为序列(a0,a1,an,)的普通母函数。iiinnxaxaxaxaaxf022110)(一、普通母函数一、普通母函数给定一个无穷序列(a0,a1,an,)(简记为an，下同)，必须注意的是，在定义4.1中，普通母函数是一个无穷级数，没有必要去讨论它的收敛性，实质上它只是引进一个表示序列的记号而已。此时变量x只是一种形式变元。对这种级数可以把它看成形式幂级数，我们可以按通常方式定义其加法、乘法、形式微分等运算，从而构成

2、一个代数体系。一个序列和它的普通母函数是一一对应的。给定了一个序列就可以得到这个序列的普通母函数。反之，如果给定了普通母函数，则序列也随之而定。由此可见，普通母函数实质上是序列的另一种表达形式。由由定义定义4.14.1可知可知解：解：由定义4.1和式(1.13)有nnnnn,2,1,0nxnnxnxnnxf21210)(nx)1(求序列 的普通母函数。由定义4.1和式(1.18)有,1)1(,21,1,01kknnnnk kkxkknxnxnnxf1)1(21101)(2nx)1(求序列的普通母函数。证明(1-4x)-1/2是序列 的普通母函数。,2,24,12,00nnn证明：证明：由牛顿二

3、项式定理式(1.16)有iixiix)4(!)121()221)(121(211)41(12/1iiixii1!)212()23)(21(41iiixii1!)12(53121iiixiiii1!)12(531!21iixiiii1!)12(531)2642(1nxnnxx224120021(1-4x)-1/2是序列 的普通母函数。,2,24,12,00nn由定义定义4.14.1知知，解：解：由式(1.20)有011nnxx023)1()1(2nnxnnx求序列序列(0，123，234，n(n+1)(n+2),)的普通母函数。将上式两边同时微分两次得 再将上式两边同乘以x得034)2)(1()

4、1(6nnxnnnx024)2)(1()1(6nnxnnnxx0)2)(1(nnxnnn214323210 xxnxnnn)2)(1(将上式两边再微分有f(x)=6x/(1-x)4是序列序列(0，123，234，n(n+1)(n+2)，)的普通母函数。由定义4.1知 由上面的例子可见，普通母函数特别适用于某些序列，尤其是包含组合数的序列，这是由于它具有牛顿二项式定理的形式。但是但是，对于具有排列数的那些序列，我们考虑下列类型的母函数(指数母函指数母函数数)更为合适。二、指数母函数指数母函数给定无穷序列(a0,a1,an,),称函数函数!2!1)(22110nxaxaxaaxfnne!0nxan

5、nnn之所以称为指数母函数是由于式(4.2)的右边很像指数函数e的幂级数展开式。注意，指数母函数也是形式幂级数。注意，指数母函数也是形式幂级数。为序列(a0,a1,an,)的指数母函数。解解：由定义4.2和式(1.7)以及例1的结论有0!),(!2)2,(!1)1,()0,()(21nxnnpxnpxnpnpxfnennxxnnxnxnn)1(2102设n是整数，求序列 的指数母函数fe(x)。例例6 6 求序列 p(0,0),p(2,1),p(4,2),p(2n,n),)的指数母函数fe(x)。!),2(!2)2,4(!1)1,2()0,0()(21nxnnpxpxppxfne121/202

6、42012(1 4)nnxxxnx 解：解：由定义4.2和式(1.7)，再利用例3的结果有例例7 7 求序列1,1,2 2,n n,的指数母函数fe(x)。其中是实数。xnnenxxxxf!2!11)(221解解：由定义4.2知n若=1，则序列(1(1，1 1，1,1,),)的指数母函数为ex。例例8 8 求序列(1(1，1 14 4，1 14 47,7,1 14 47 7(3n+1),(3n+1),)的指数母函数。!2)741(!1)41(1)(21xxxfe!)13(741nxnnnnxnn0!)13(7413/4)31(x解：解：由定义4.2和二项式定理式(1.16)有 由定义4.2易见

7、，序列(a(a0 0,a,a1 1,a,an n,)的指数母函数也是序列(a(a0 0,a,a1 1,a,a2 2/2!,/2!,a,an n/n!,/n!,)的普通母函数。这说明普通母函数与指数母函数之间有着密切的联系，这种联可由下面的定理表出。设f(x),fe(x)分别是序列(a(a0 0,a,a1 1,a,an n,)的普通母函数和指数母函数，则dssxfexfes)()(0!)()(0nsxasxfnnne证明：证明：由指数母函数的定义,有dssenxadsnxsaedssxfensnnnnnnnss 00000!)(!0ndssens)()(00 xfxadssxfennnes将上式两边同乘以e e-s-s并从0到积分得由分部积分法有由分部积分法有证毕证毕故故