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 实例
应用(生成函数求法) 例4红、白、兰涂色1Xn的方格,要求偶数个为白色, 问有多少方案? 解设方案数为an G2(x)=(+x,+…)(1+x+m+… (ee e e-+-e ∑3"n+,∑=∑ +1x n=0 ni 2 nk 3n+1
6 例 4 红、白、兰涂色 1×n 的方格，要求偶数个为白色， 问有多少方案？ 解 设方案数为 an 2 3 1 2 ! 3 1 2 ! 1 ! 3 2 1 2 1 2 1 ( ) 21 ...) 2! ...)(1 2! ( ) (1 0 0 0 2 3 2 2 2 + = + = + = = + = + = + + + + + ∑ ∑ ∑ ∞ = ∞ = ∞ = − n n n n n n n n n n x x x x x e a n x n x n x e e e e e x x x G x 应用（生成函数求法）
递推方程的求法 解法2递推方程 an=2an1+(3-an1) =2 an=amn-1t3 解得P=3/2,an=32 通解an=C+32 代入初值得C=1/2 解为an=(3+1)2
7 解法 2 递推方程 an = 2an-1 + (3n-1− an-1) a1 = 2 an = an-1 + 3n-1 a * n = P3n-1, 解得 P = 3/2, a*n = 3n/2 通解 an = C + 3n/2 代入初值得 C = 1/2 解为 an = (3n+1)/2 递推方程的求法
2.6高级计数 高级计数 Catalan数 第一类 Stirling数 第二类 Stirling数 讨论要点 定义 递推方程 恒等式 对应的组合问题 生成函数
8 22.6 高级计数 高级计数 Catalan数 第一类Stirling数 第二类Stirling数 讨论要点 定义 递推方程 恒等式 对应的组合问题 生成函数
Catalan数定义 定义一个凸n+1边形,通过不相交于n+1边形内 部的对角线把n+1边形拆分成的三角形个数,记 作hn,称为 Catalan数. 实例:h2h3=2, h:=5 △②公
9 Catalan数定义 定义 一个凸 n+1 边形，通过不相交于n+1边形内 部的对角线把 n +1边形拆分成的三角形个数，记 作hn，称为Catalan数. 实例：h2=1, h3=2, h4=5
递推方程 考虑n+1条边的多边形,端点A1,An1的边记为a, 以Ak+1(k=-1,2,,n-1)A1为边,An+14k+为另 边,构成三角形T,T将多边形划分成R1和R2两个 部分,分别为k+1边形和nk+1边形 k+1 hn=∑h m-k,n≥2 k=1 R R 2 2n-2 An n(n-1 A a+1
10 考虑 n+1 条边的多边形，端点 A1, An+1的边记为 a, 以 Ak+1（k=1, 2,…, n-1）A1为边，An+1Ak+1 为另一 边，构成三角形 T, T 将多边形划分成 R1和 R2两个 部分，分别为 k+1 边形和 n-k+1 边形. 1 , 2 1 1 1 = = ∑ ≥ − = − h h h h n n k n k n k ⎟⎟⎠⎞ ⎜⎜⎝⎛ −− = 1 1 2 2 nn n hn 递推方程
