122 指数型生成函数.ppt

《122 指数型生成函数.ppt》由会员分享，可在线阅读，更多相关《122 指数型生成函数.ppt（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、12.2 指数型生成函数,用生成函数可以解决组合计数问题，那么是否可用来解决排列问题？注意到组合计数问题，多重集S=a1,a2, ak的r-组合数是C(r+k-1,r)，数列C(r+k-1,r)的生成函数,收敛于初等函数,而对于集合a1,a2,an的r-排列数为p(n,r), 数列p(n,r)的生成函数,其收敛和函数不能表示为初等函数，因此无法直接应用。但因为C(n,r)=p(n,r)/r!，所以,对排列数的生成函数可考虑用这样的幂级数,指数型生成函数,定义12.2:设a0,a1,an,是一个数列，构造形式幂级数,称f(x)是数列a0,a1,an,的指数型生成函数为什么要称指数型生成函数?因为

2、,与上述幂级数类似。,根据定义知，指数型生成函数与幂级数型生成函数的一般项仅相差一个因子1/n!只要令 ar=ar/r!，则ar的幂级数型生成函数就是ar的指数型生成函数，因此由定理12.1易得指数型生成函数的性质。定理12.2：设an,bn的指数生成函数分别为fe(x)和ge(x)，则：,对于an=1的数列1，它的指数型生成函数为：,现在用指数型生成函数来解决多重集的排列问题。定理12.3：设有限多重集n1a1,n2a2, nkak，且n=n1+n2+nk，对任意的非负整数r，ar为S的r-排列数，则数列ar的指数型生成函数为：g(x)=gn1(x)g n2(x)gnk，其中gni(x)=1

3、+x+x2/2!+ +xni/ni!,i=1,2,k。证明：要证ar的指数型生成函数为gn1(x)gn2(x)gnk，关键是证明gn1(x)gn2(x) gnk(x)的展开式中项xr/r!的系数就是ar。,下面考察gn1(x)g n2(x)gnk的展开式中项xr/r!的情况。,上述式子乘积的每项：,下面证明,就是S的r-排列数ar。,而对于S的每个r-排列，其确定了ai(i=1,2,k)的个数，因此是某个r元子集的一个全排列。S的r-排列数不会多于S的所有r元子集的全排列数之和。所以S的r-排列数ar就是,即gn1(x)g n2(x)gnk=g(x)。,例：S=1a1,1a2,1ak,求r-排

4、列数解：设排列数为pr, gri(x)=1+x，则,所以pr=n!/(n-r)!=p(n,r),例：S=a1,a2,ak，求S的r-排列数解：设排列数为pr, gri(x)=(1+x+x2/2!+xr/r!+)，则g(x)=(1+x+x2/2!+xr/r!+)k=(ex)k=ekx,所以pr=kr。,例：S=2x1,3x2，求4-排列数。解：设4-排列数为p4,数列pr的指数型生成函数为g(x)=(1+x+x2/2!)(1+x+x2/2!+x3/3!),p4=?要注意标准形式: pr是xr/r!的系数。所以,因此p4=10。,3!=6,4!=24,5!=120,例：S=2x1,3x2,4x3，

5、求4-排列数，且各元素均出现偶数次。解：设4-排列数为p4, 数列pr的指数型生成函数为g(x)=(1+x2/2!)(1+x2/2!)(1+x2/2!+x4/4!),所以p4=4*3+3*2+1=19,例：设有6个数字，其中 3 个数字 1,2个数字6,1个数字8，问能组成多少个四位数?解：这实际上是求S=3x1,2x2,1x3中取4个的多重集排列数问题。其指数型生成函数为：g(x)=(1+x+x2/2!+x3/3!)(1+x+x2/2!)(1+x)=1+3x+8(x2/2!)+19(x3/3!)+38(x4/4!)+60(x5/5!)+60(x6/6!)由此可得a4=38，即可组成38个四位数。,设S=a1,a2, a3，要求a3出现偶数次，a2至少出现1次。求满足上述要求的r-排列数。,作业:P253:3,4,7,8,12,