离散数学-103-4指数生成函数及其应用.ppt

课件,1,指数生成函数的定义与实例指数生成函数的性质指数生成函数的应用,10.3 指数生成函数及其应用,课件,2,指数生成函数的定义与实例,例1 给定正整数m,an=P(m,n),an的指数生成函数为,例2 bn=1,则bn的指数生成函数为,定义10.7 设an为序列，称,为an的指数生成函数.,课件,3,指数生成函数的性质,设数列an,bn的指数生成函数分别为Ae(x)和Be(x),则,其中,证,课件,4,指数生成函数的应用 多重集排列计数,定理10.8 设 S=n1a1,n2a2,nkak为多重集，则 S 的 r 排列数的指数生成函数为,课件,5,证明,考察指数生成函数展开式中 xr 的项,其中 m1+m2+mk=r 0 mi ni,i=1,2,k（*）,其中求和是对满足方程（*）的一切非负整数解来求.一个非负整数解对应了m1a1,m2a2,mkak，即S的r组合,而该组合的全排列数是，ar是 S的r排列数.,课件,6,实例,例3 由1,2,3,4 组成的五位数中，要求1出现不超过2次，但不能不出现，2出现不超过1次，3出现可达3次，4出现偶数次.求这样的五位数个数.解,N=215,课件,7,实例(续),例4 红、白、兰涂色 1n 的方格，要求偶数个为白色，问有多少方案？解 设方案数为an,课件,8,10.4 Catalan数与Stirling数,Catalan数第一类 Stirling数第二类 Stirling数,课件,9,Catalan数的定义,定义10.8 一个凸 n+1边形，通过不相交于n+1 边形内部的对角线把 n+1 边形划分成三角形，划分方案个数记作hn，称为Catalan数.,实例：h4=5,初值 h2=1,课件,10,Catalan数的递推方程,考虑n+1条边的多边形，端点A1,An+1的边记为a,对于任意的 k=1,2,n1，以Ak+1A1为边，An+1Ak+1为另一边，与a构成三角形T,T 将多边形划分成 R1和 R2两个部分，分别为 k+1 边形和 nk+1边形.,递推方程,课件,11,Catalan数对应的组合问题,从(0,0)到(n,n)的除了端点以外不接触对角线的非降路 径数 2hn a1a2an,不改变因子顺序，加括号的方法数 hn n 片树叶的有序三度根树个数 hn 2n 个点均匀分布在圆周上，用 n 条不相交的弦配对的 方法数 hn+1 n个数的堆栈的不同输出个数hn+1,课件,12,实例计数堆栈的输出个数,例1 1,2,n放入堆栈后的不同的输出个数,解 在 1 进栈到出栈之间作为一个子问题，1出栈后作为一个子问题.过程如下：,步2：子问题规模 k，步4：子问题规模 nk1,11进栈；2处理 k个数（2,k+1）的进栈问题；31出栈；4处理 k+2,n 的进栈问题；,课件,13,计数堆栈的输出个数(续),课件,14,第一类Stirling数,将 xr 系数的绝对值 Sr 记作，称为第一类 Stirling数,定义10.9 多项式 x(x1)(x2)(xn+1)的展开式为 Snxn Sn1xn1+Sn2xn2+(1)n1S1x,实例 x(x1)=x2x x(x1)(x2)=x33x2+2x,课件,15,第一类Stirling数的递推方程,课件,16,第一类Stirling数的恒等式,课件,17,第二类Stirling数的定义,课件,18,第二类Stirling数的递推方程,课件,19,第二类Stirling数的恒等式,课件,20,恒等式证明,课件,21,恒等式证明(续),课件,22,函数与关系的计数,课件,23,n个球放到m个盒子的方法计数,