12.2 指数型生成函数 用生成函数可以解决组合计数问题，那么是否可用来解决排列问题？

Presentation on theme: "12.2 指数型生成函数 用生成函数可以解决组合计数问题，那么是否可用来解决排列问题？"— Presentation transcript:

1 12.2 指数型生成函数 用生成函数可以解决组合计数问题，那么是否可用来解决排列问题？
注意到组合计数问题，多重集S={·a1,·a2,…, ·ak}的r-组合数是C(r+k-1,r)，数列{C(r+k-1,r)}的生成函数 收敛于初等函数

2 而对于集合{a1,a2,…,an}的r-排列数为p(n,r), 数列{p(n,r)}的生成函数
其收敛和函数不能表示为初等函数，因此无法直接应用。 但因为C(n,r)=p(n,r)/r!，所以 对排列数的生成函数可考虑用这样的幂级数 指数型生成函数

3 定义12.2:设a0,a1,,an,是一个数列，构造形式幂级数
称f(x)是数列a0,a1,,an,的指数型生成函数 为什么要称指数型生成函数? 因为 与上述幂级数类似。

4 根据定义知，指数型生成函数与幂级数型生成函数的一般项仅相差一个因子1/n!
只要令 a'r=ar/r!，则a'r的幂级数型生成函数就是ar的指数型生成函数，因此由定理12.1易得指数型生成函数的性质。 定理12.2：设an,bn的指数生成函数分别为fe(x)和ge(x)，则： 对于an=1的数列{1}，它的指数型生成函数为：

5 现在用指数型生成函数来解决多重集的排列问题。
定理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。

6 下面考察gn1(x)·g n2(x)·…·gnk的展开式中项xr/r!的情况。
上述式子乘积的每项：

7 即gn1(x)·g n2(x)·…·gnk=g(x)。
下面证明 就是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)。

8 例：S={1·a1,1·a2,…,1·ak},求r-排列数
解：设排列数为{pr}, gri(x)=1+x，则 所以pr=n!/(n-r)!=p(n,r)

9 例：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。

10 例：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!的系数。 所以 3!=6, 4!=24, 5!=120 因此p4=10。

11 例：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

12 例：设有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个四位数。

13 设S={·a1,·a2, ·a3}，要求a3出现偶数次，a2至少出现1次。求满足上述要求的r-排列数。

14 作业:P253:3,4,7,8,12