2.5指数生成函数 定义设{an}为序列,称 G(x)=∑a 为{an}的指数生成函数 例1给定正整数m2an=P(m,n,{an的指数生成函数为 x)=∑P( n. mEnlm-lle-"s ∑ ∑。"=(1 ∥=0(n 例2b=1,则{b}的指数生成函数为 x)=∑ e -=0 nl
1 定义 设{an}为序列，称 ∑ ∞ = = n 0 n e n n x G x a ! ( ) 为{an}的指数生成函数. 例 1 给定正整数 m, an = P(m,n), {an}的指数生成函数为 ∑∑ ∑ ∞ = ∞ = ∞ = = + ⎟⎟⎠⎞ ⎜⎜⎝⎛ = − = = 00 0 (1 ) !( )! ! ! ( ) ( , ) nn n n n m n e x x nm x n m n m nx G x P m n 例 2 bn=1, 则{ bn}的指数生成函数为 ∑ ∞ = = = 0 ! ( ) n x n e e n x G x 22.5 指数生成函数
指数生成函数的性质 设数列{an,b的指数生成函数分别为A(x)和B2(x),则 A(x),B(x)=∑cn ,其中Cn kun-k 证 x x ∑ A(x),B(x)=(∑k(∑b) : k=0 k x"na nlb ∑x"∑ k 1=0 k=0k!(n-k). h=0n!k=0k!(n-k) x n-k
2 设数列{an},{bn}的指数生成函数分别为 Ae(x)和 Be(x), 则 ! ( ) ( ) 0 nx A x B x c n n e e ∑ n ∞= ⋅ = ,其中 ∑= ⎟ − ⎟⎠⎞ ⎜⎜⎝⎛ = nk n k n k a b kn c 0 证： ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∞ = = − ∞ = = − ∞ = = − ∞ = ∞ = ∞ = ⎟⎟⎠⎞ ⎜⎜⎝⎛ = − = ⋅ − = ⋅ = ⋅ = ⋅ 0 0 0 0 0 0 0 0 0 ! ( )! ! ! ( )! ! ! ) ! ) ( ! ( ) ( ) ( ! n n k k n k n n n k k n k n n n k n k n k l l l k k e e k n n n a b k n n x n k n b k a n x n k b k a x l x b k x A x B x a n x c 指数生成函数的性质
应用-多重集排列计数 设S={n1an,m2a2…,nka}为多重集, 则S的r排列数{a}的指数生成函数为 Ge(x)=fn,(x)fn(x).fn, (r) Jn(x)=1+x++…+,i=1,2,…,k 2
3 设 S={ n1⋅a1, n2⋅a2, … , nk⋅ak }为多重集， 则 S 的 r 排列数{ ar }的指数生成函数为 i k n x x f x x G x f x f x f x i n n e n n n i i k 1, 2, ... , ! ... 2! ( ) 1 ( ) ( ) ( ) ... ( ) 2 1 2 = + + + + = = 应用-多重集排列计数
证明 考察指数生成函数展开式中x的项, i vm2 x 其中m+m2+…+mk=r 0≤m≤nl;i=1,2,…,k m1++…+m x 即 1.m2:3…mlk mi m,!.mk 其中求和是对满足方程(*)的一切非负整数解来求 一个非负整数解对应了{ma,m2m2,…,mka},即S的r组合 而该组合的全排列数是 ,因此an代表了S的r排列数
4 考察指数生成函数展开式中 x r的项， ! ... ! ! 1 2 1 2 k m m m m x m x m x k ， 其中 m 1 + m2 + … + m k= r 0 ≤ mi ≤ ni, i = 1, 2, … , k （ * ） 即 ! !... ! ! ! ... ! ! 1 2! 1 2 ... 1 2 k r k m m m m m m r r x m m m x k = + + + ，ar = ∑ ! !... ! ! m 1 m 2 m k r 其中求和是对满足方程（ *）的一切非负整数解来求. 一个非负整数解对应了{ m 1⋅a 1, m 2⋅a 2, … , m k⋅ak }，即 S 的 r 组合 而该组合的全排列数是 ! !... ! ! m 1 m 2 m k r ，因此 a r代表了 S 的 r 排列数. 证明
实例 例3由1,2,34组成的五位数中,要求 1出现不超过2次,但不能不出现,2出现不超过1次, 3出现可达3次,4出现偶数次求这样的五位数个数 解: G2(x)=(x+,)(1+x)1+x+ 3× 4 x =x+5—+18—+64—+215—+, 2,3,4! N=215
5 例 3 由 1,2,3,4 组成的五位数中，要求 1 出现不超过 2 次，但不能不出现，2 出现不超过 1 次， 3 出现可达 3 次，4 出现偶数次.求这样的五位数个数. 解： ... 5! 215 4! 64 3! 18 2! 5 ) 2! 4! )(1 2! 3! )(1 )(1 2! ( ) ( 2 3 4 5 2 2 3 2 4 = + + + + + = + + + + + + + x x x x x x x x x x x x Ge x x N = 215 实例