10.3-4指数生成函数及其应用[上课课堂]

1、10.3 指数生成函数及其应用 指数生成函数的定义与实例指数生成函数的定义与实例 指数生成函数的性质指数生成函数的性质 指数生成函数的应用指数生成函数的应用 1 课程章节 指数生成函数的定义与实例 00 0 )1( )!( ! ! ! ),()( n mn n n n n e xx n m x nmn m n x nmPxG 例例1 给定正整数给定正整数m, an = P(m,n), an的指数生成函数为的指数生成函数为 0 ! )( n x n e e n x xG 例例2 bn=1, 则则bn的指数生成函数为的指数生成函数为 0 0n n ne n x axG ! )(定义定义10.7 设

2、设an为序列，称为序列，称 为为 an 的的指数生成函数指数生成函数. . 2 课程章节 指数生成函数的性质 ! )()( 0 n x cxBxA n n nee 设数列设数列an, bn的指数生成函数分别为的指数生成函数分别为Ae(x)和和Be(x), 则则 n k knkn ba k n c 0 其中其中 00 0000 000 ! )!( ! !)!(! ) ! () ! ()()( ! n n k knk n n n k knk n n n k knkn l l l k k kee n n n ba k n n x kn bn k a n x kn b k a x l x b k x

3、axBxA n x c 证证 3 课程章节 指数生成函数的应用 多重集排列计数 定理定理10.8 设设 S = n1 a1, n2 a2, , nk ak为多重集，则为多重集，则 S 的的 r 排列数的指数生成函数为排列数的指数生成函数为 ki n xx xxf xfxfxfxG i n n nnne i i k ,., 2, 1 ! . ! 2 1)( )(.)()()( 2 21 4 课程章节 证明 !.! ! !.! 21!21 . 21 k r k mmm mmm r r x mmm x k !.! ! 21k r mmm r a ! . ! 21 21 k mmm m x m x m

4、 x k 考察指数生成函数展开式中考察指数生成函数展开式中 xr 的项的项 其中其中 m1 + m2 + + mk= r 0 mi ni, i = 1, 2, , k （*） 其中求和是对满足方程（其中求和是对满足方程（*）的一切非负整数解来求）的一切非负整数解来求. 一个非负整数解对应了一个非负整数解对应了m1 a1, m2 a2,mk ak，即，即S的的r组合组合 !.! ! 21k mmm r 而该组合的全排列数是而该组合的全排列数是 ，ar是是 S的的r排列数排列数. 5 课程章节 实例 . ! 5 215 ! 4 64 ! 3 18 ! 2 5 ) ! 4! 2 1)( ! 3! 2

5、 1)(1)( ! 2 ()( 5432 42322 xxxx x xxxx xx x xxGe 例例3 由由1, 2, 3, 4 组成的五位数中，要求组成的五位数中，要求1出现不超过出现不超过2次，次， 但不能不出现，但不能不出现，2出现不超过出现不超过1次，次，3出现可达出现可达3次，次，4出出 现偶数次现偶数次. 求这样的五位数个数求这样的五位数个数. 解解 N = 215 6 课程章节 实例(续) 例例4 红、白、兰涂色红、白、兰涂色 1 n 的方格，要求偶数个为白色，的方格，要求偶数个为白色， 问有多少方案？问有多少方案？ 解解 设方案数为设方案数为an 2 13 !2 13 !2

6、1 ! 3 2 1 2 1 2 1 )( 2 1 .) ! 2 1.)( ! 2 1()( 000 32 2 22 n n n nn nn nn n xxxxx e a n x n x n x eeeee x x x xG 7 课程章节 10.4 Catalan数与Stirling数 CatalanCatalan数数 第一类第一类 StirlingStirling数数 第二类第二类 StirlingStirling数数 8 课程章节 Catalan数的定义 定义定义10.8 一个凸一个凸 n+1边形，通过不相交于边形，通过不相交于n+1 边形内边形内 部的对角线把部的对角线把 n+1 边形划分

7、成三角形，划分方案个数边形划分成三角形，划分方案个数 记作记作hn，称为，称为Catalan数数. 实例：实例：h4=5 初值初值 h2=1 9 课程章节 Catalan数的递推方程 考虑考虑n+1条边的多边形，端点条边的多边形，端点A1, An+1的边记为的边记为a, 对于任意对于任意 的的 k=1, 2, n 1，以，以Ak+1A1为边，为边，An+1Ak+1为另一边，与为另一边，与a 构成三角形构成三角形T, T 将多边形划分成将多边形划分成 R1和和 R2两个部分，分别两个部分，分别 为为 k+1 边形和边形和 n k+1边形边形. 1 2, 1 1 1 h nhhh n k knkn

8、 1 221 n n n hn 递推方程递推方程 10 课程章节 Catalan数对应的组合问题 从从(0,0)到到(n,n)的除了端点以外不接触对角线的非降路的除了端点以外不接触对角线的非降路 径数径数 2hn a1 a2 an, 不改变因子顺序，加括号的方法数不改变因子顺序，加括号的方法数 hn n 片树叶的有序三度根树个数片树叶的有序三度根树个数 hn 2n 个点均匀分布在圆周上，用个点均匀分布在圆周上，用 n 条不相交的弦配对的条不相交的弦配对的 方法数方法数 hn+1 n个数的堆栈的不同输出个数个数的堆栈的不同输出个数hn+1 11 课程章节 实例计数堆栈的输出个数 1)1( )1(

9、)()( 1 0 T knTkTnT n k 例例1 1, 2, , n放入堆栈后的不同的输出个数放入堆栈后的不同的输出个数 解解 在在 1 进栈到出栈之间作为一个子问题，进栈到出栈之间作为一个子问题，1出栈后作出栈后作 为一个子问题为一个子问题. 过程如下：过程如下： 步步2：子问题规模：子问题规模 k，步，步4：子问题规模：子问题规模 n k 1 11进栈；进栈； 2处理处理 k个数（个数（2, , k+1）的进栈问题；）的进栈问题； 31出栈；出栈； 4处理处理 k+2, , n 的进栈问题；的进栈问题； 12 课程章节 计数堆栈的输出个数(续) n n n nTx n n n xG x

10、xxGG xxxGxGxxG x xG xnT knTkTxxlTxkTXG xnTxG TT knTkTnT n n n n n kn n l l k k n n n k 2 1 1 )(, 2 1 1 )( 411)(2, 0)0( ,411)(201)()( 1)( )( ) )1()()( )()( ,)()( 1)1(, 1)0( )1()()( 0 2 1 1 1 01 1 00 2 0 1 0 由于由于 13 课程章节 第一类Stirling数 将将 xr 系数的绝对值系数的绝对值 Sr 记作记作 ，称为，称为第一类第一类 Stirling数数 r n 1 3 3 , 3 2 3

11、 , 2 1 3 , 0 0 3 1 2 2 , 1 1 2 , 0 0 2 定义定义10.9 多项式多项式 x(x 1)(x 2)(x n+1) 的展开式为的展开式为 Snxn Sn 1xn 1+ Sn 2xn 2 + ( 1)n 1S1x 实例实例 x(x 1) = x2 x x(x 1)(x 2) = x3 3x2+2x 14 课程章节 第一类Stirling数的递推方程 15 课程章节 第一类Stirling数的恒等式 16 课程章节 第二类Stirling数的定义 17 课程章节 第二类Stirling数的递推方程 18 课程章节 第二类Stirling数的恒等式 n i m k n m m n r i i n r n mk k n k m nnnn m n m