122 指数型生成函数.ppt

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,的指数型生成函数为什么要称指数型生成函数?因为,与上述幂级数类似。,根据定义知，指数型生成函数与幂级数型生成函数的一般项仅相差一个因子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的r-排列数，则数列ar的指数型生成函数为：g(x)=gn1(x)·g n2(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)·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=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-排列数为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,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,