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
下面考察gn1(x)gn2(x)……gn的展开式中 项xr/r!的情况。 g(x)=1+x × X ∴· 2! 1 x来源8(x)=1+xx…×十 2 X 8(x)=1+x+ k 上述式子乘积的每项:xx..xm=xm
下面考察gn1(x)·g n2(x)·…·gnk的展开式中 项x r /r!的情况。 = + + + + = + + + + = + + + + 2! ! ( ) 1 2! ( ) 1 2! ! ( ) 1 2 2 2 1 2 2 2 1 1 k n r n r n r r n x x g x x n x x g x x n x x g x x x k k 来源 上述式子乘积的每项： ! ! ! ! ! ! 1 2 1 2 1 2 1 2 k m m m k m m m m m m x m x m x m x k k + ++ =
下面证明∑ m+m2+m一m1!m2 就是S的r排列数a。 而对于S的每个r排列,其确定了 a1(i=1,2,k)的个数,因此是某个r元子集 的一个全排列。S的r排列数不会多于S 的所有r元子集的全排列数之和。 所以S的r排列数a1就是 ∑ mn1+m2+…·mlk= mn1!m)!…·m k m.≥0 即gn1(x),gn2(x)…gn=g(x)
下面证明 + + = 0 1 2 1 2 ! ! ! ! i k m m m m r m m mk r 就是S的r-排列数ar。 而对于 S 的每个 r- 排 列 ， 其确定了 ai (i=1,2,…k)的个数，因此是某个r元子集 的一个全排列。S的r-排列数不会多于S 的所有r元子集的全排列数之和。 所以S的r-排列数ar就是 + + = 0 1 2 1 2 ! ! ! ! i k m m m m r m m mk r 即gn1 (x)·g n2 (x)·…·gnk =g(x)
例:S={1·a1a2…,1a},求r排列数 解:设排列数为{pn},gn(x)=1+x,则 g(x)=(1+x)=∑C(m,r)x7 ∑ r=0 !(n-r) n! x r=o(n-r 所以p=n!(a-r)!=p(n,r)
例：S={1·a1 ,1·a2 ,…,1·ak },求r-排列数 解：设排列数为{pr }, gri(x)=1+x，则 = = = − = − = = + = k r r k r r k r k r r x n r n x r n r n g x x C n r x 0 0 0 ( )! ! ! !( )! ! ( ) (1 ) ( , ) 所以pr=n!/(n-r)!=p(n,r)
例:S={∞a1a2…,·a1},求S的r排列数 解:设排列数为{p} gA(x)=(1+x+x2/2+….+xr!+.),则 g(x)=(1+x+x2/2!+…+x/r!+…,)k=(ex)k=ek (hr) ∑=∑k 0 所以p=ko
例：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 = = = = 0 0 ! ! ( ) r r r r r r x k r kx 所以pr=kr
例:S={2x1,3·x2},求4-排列数。 解:设4排列数为p4数列{p}的指数型生成函 数为 g(x)=(1+x+x2/2)(1+x+x2/2+x3/3!) =1+2x+(+x2+)+ 2I 3!212!213 7 1+2x+2x2+-x3+x4+-x 要注意标准形式:p是xr的系数。 3!=6, 所以 8(x)=1+2x+4 4!=24 +7 +2×5+10 5!=120 因此p4=10
例：S={2·x1 ,3·x2 }，求4-排列数。 解：设4-排列数为p4 ,数列{pr }的指数型生成函 数为 g(x)=(1+x+x2 /2!)(1+x+x2 /2!+x3 /3!) 2 3 4 5 2 3 3 3 4 4 5 2 2 1 2 1 1 2 5 6 7 1 2 2 2!3! ) 3! 2!2! ) ( 3! 2! 2! ) ( 2! 2! 1 2 ( x x x x x x x x x x x x x x x = + + + + + = + + + + + + + + + + p4=? 要注意标准形式: pr是xr /r!的系数。 所以 5! 10 4! 2 5 3! 7 2! ( ) 1 2 4 2 3 4 5 x x x x g x = + x + + + + 因此p4=10。 3!=6, 4!=24, 5!=120