122 指数型生成函数

《122 指数型生成函数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、的r-排列数，则数列ar的指数型生成函数为：g(x)=gn1(x)·gn2(x)·…·gnk，其中gni(x)=1+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)·gn2(x)·…·gnk的展开式中项xr/r!的情况。上述式子乘积的每项：下面证明就是S的r-排列数ar。而对于S的每个r-排列，其确定了ai(i=1,2,…k)的个数，因此是某个r元子集的一个全排列。S的r

4、-排列数不会多于S的所有r元子集的全排列数之和。所以S的r-排列数ar就是即gn1(x)·gn2(x)·…·gnk=g(x)。例：S={1·a1,1·a2,…,1·ak},求r-排列数解：设排列数为{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={2·x1,3·x2}，求4-排列数。解：设4-

5、排列数为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={2·x1,3·x2,4·x3}，求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={3·x1,

6、2·x2,1·x3}中取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