122指数型生成函数 用生成函数可以解决组合计数问题,那 么是否可用来解决排列问题? 注意到组合计数问题,多重集 S={a1,22y…,∞a1 }的r组合数是 C(r+k-1,r),数列(C(r+k-1,r)的生成函数 C(k+r-1,)y=(1-y) ∑ 收敛于初等函数
12.2 指数型生成函数 用生成函数可以解决组合计数问题，那 么是否可用来解决排列问题？ 注 意 到 组 合 计 数 问 题 ， 多重集 S={·a1 ,·a2 ,…, ·ak } 的 r- 组合数是 C(r+k-1,r)，数列{C(r+k-1,r)}的生成函数 k r r y C k r r y (1 ) 1 ( 1, ) 0 − + − = = 收敛于初等函数
而对于集合{a1a2…,an}的r排列数为pn,r) 数列{p(n,r)}的生成函数∑p(n,)y 其收敛和函数不能表示为初等函数,因此 无法直接应用。 但因为C(n,r)=p(n,r)r!,所以 (1+x)=∑C(n1)x=∑m 对排列数的生成函数可考虑用这样的幂级数 指数型生成函数
而对于集合{a1 ,a2 ,…,an }的r-排列数为p(n,r), 数列{p(n,r)}的生成函数 =0 ( , ) r r p n r y 其收敛和函数不能表示为初等函数，因此 无法直接应用。 但因为C(n,r)=p(n,r)/r!，所以 = = + = = n r n r r n r r x x C n r x p n r 0 0 ! (1 ) ( , ) ( , ) 对排列数的生成函数可考虑用这样的幂级数 = n r r r r x a 0 ! 指数型生成函数
定义122:设a0a1,an是一个数列,构 造形式幂级数 f(x)=∑x=ao+a1x+x2+…+xn+ 称(x)是数列a,a1 ··9n 号·●● 的指数型生成函数 为什么要称指数型生成函数? 因为aa=y=(ax 与上述幂级数类似。 r=0
定义12.2:设a0 ,a1 ,,an ,是一个数列，构 造形式幂级数 = = + + ++ + = n n r r r x n a x a x a a x r a f x ! 2! ! ( ) 2 2 0 1 0 称f(x)是数列a0 ,a1 ,,an ,的指数型生成函数 为什么要称指数型生成函数? 因为 = = = 0 ! ( ) r r ax r ax e 与上述幂级数类似
根据定义知,指数型生成函数与幂级数 型生成函数的一般项仅相差一个因子1/m 只要令a'=a/r!,则a',的幂级数型生成 函数就是a,的指数型生成函数,因此由 定理12.1易得指数型生成函数的性质。 定理122:设a1,bn的指数生成函数分别 为f(x)和g(x),则: f(x)·g2(x)=∑Cn 对于an=1的数列{1},它 0 的指数型生成函数为: 其中cn=∑C(n,k)akbn-k k=0 ∑ 1+x+—++—+
根据定义知，指数型生成函数与幂级数 型生成函数的一般项仅相差一个因子1/n! 只要令 a'r=ar /r!，则a'r的幂级数型生成 函数就是ar的指数型生成函数，因此由 定理12.1易得指数型生成函数的性质。 定理12.2：设an ,bn的指数生成函数分别 为fe (x)和ge (x)，则： = − = = • = n k n k n k n n e e n c C n k a b n x f x g x c 0 0 ( , ) ! ( ) ( ) 其中 对于an=1的数列{1}，它 的指数型生成函数为： = = = + + ++ + = 2! ! 1 ! 2 0 n x x x r x e n r r x
现在用指数型生成函数来解决多重集的排 列问题。 定理12.3:设有限多重集{n1a1,n2a2 na},且n=n1+n2+…+n1,对任意的非负整 数r,a1为S的r排列数,则数列a1的指数型 生成函数为:g(x)=gn1(x)gn2(x) °··nk 其 中gn1(x)=1+x+x2!+..+x/mn1,i=1,2 证明:要证a的指数型生成函数为 gn1(x)gn2(x)…gnk 关键是证明gn1(x)gn2(x)…gn(x)的展开式 中项xr的系数就是a
现在用指数型生成函数来解决多重集的排 列问题。 定理1 2 .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)的展开式 中项x r /r!的系数就是ar