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

《离散数学-103-4指数生成函数及其应用.ppt》由会员分享，可在线阅读，更多相关《离散数学-103-4指数生成函数及其应用.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、指数生成函数的定义与实例指数生成函数的定义与实例指数生成函数的性质指数生成函数的性质指数生成函数的应用指数生成函数的应用 指数生成函数及其应用指数生成函数及其应用1指数生成函数的定义与实例指数生成函数的定义与实例例例1 给给定正整数定正整数m,an=P(m,n),an的指数生成函数的指数生成函数为为 例例2 bn=1,则则bn的指数生成函数的指数生成函数为为定定义义10.7 设设an为为序列，称序列，称为为 an 的的指数生成函数指数生成函数.2指数生成函数的性质指数生成函数的性质设设数列数列an,bn的指数生成函数分的指数生成函数分别为别为Ae(x)和和Be(x),则则 其中其中证证3指数生

2、成函数的应用指数生成函数的应用 多重集排列计数多重集排列计数定理定理 设设 S=n1 a1,n2 a2,nk ak为为多重集，多重集，则则 S 的的 r 排列数的指数生成函数排列数的指数生成函数为为4证证明明考察指数生成函数展开式中考察指数生成函数展开式中 xr 的的项项其中其中 m1+m2+mk=r 0 mi ni,i=1,2,k （*）其中求和是其中求和是对满对满足方程（足方程（*）的一切非）的一切非负负整数解来求整数解来求.一个非一个非负负整数解整数解对应对应了了m1 a1,m2 a2,mk ak，即，即S的的r组组合合而该组合的全排列数是而该组合的全排列数是 ，ar是是 S的的r排列数

3、排列数.5实例实例例例3 由由1,2,3,4 组组成的五位数中，要求成的五位数中，要求1出出现现不超不超过过2次，次，但不能不出但不能不出现现，2出出现现不超不超过过1次，次，3出出现现可达可达3次，次，4出出现现偶数次偶数次.求求这样这样的五位数个数的五位数个数.解解 N=2156实例实例(续续)例例4 红红、白、白、兰兰涂色涂色 1 n 的方格，要求偶数个的方格，要求偶数个为为白色，白色，问问有多少方案？有多少方案？解解 设设方案数方案数为为an 710.4 Catalan数与数与Stirling数数Catalan数数第一类第一类 Stirling数数第二类第二类 Stirling数数8C

4、atalan数的定义数的定义定义定义 一个凸一个凸 n+1边形，通过不相交于边形，通过不相交于n+1 边形内部的边形内部的对角线把对角线把 n+1 边形划分成三角形，划分方案个数记作边形划分成三角形，划分方案个数记作hn，称为，称为Catalan数数.实例：实例：h4=5初值初值 h2=1 9Catalan数的递推方程数的递推方程考考虑虑n+1条条边边的多的多边边形，端点形，端点A1,An+1的的边记为边记为a,对对于任意于任意的的 k=1,2,n 1，以，以Ak+1A1为边为边，An+1Ak+1为为另一另一边边，与，与a构成三角形构成三角形T,T 将多将多边边形划分成形划分成 R1和和 R2

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

6、计数堆栈的输出个数计数堆栈的输出个数例例1 1,2,n放入堆栈后的不同的输出个数放入堆栈后的不同的输出个数 解解 在在 1 进栈到出栈之间作为一个子问题，进栈到出栈之间作为一个子问题，1出栈后作出栈后作为一个子问题为一个子问题.过程如下：过程如下：步步2：子问题规模：子问题规模 k，步，步4：子问题规模：子问题规模 n k 1 11进栈；进栈；2处理处理 k个数（个数（2,k+1）的进栈问题；）的进栈问题；31出栈；出栈；4处理处理 k+2,n 的进栈问题；的进栈问题；12计数堆栈的输出个数计数堆栈的输出个数(续续)13第一类第一类Stirling数数将将 xr 系数的绝对值系数的绝对值 Sr

7、 记作记作 ，称为，称为第一类第一类 Stirling数数定定义义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数的恒等式数的恒等式19恒等式证明恒等式证明20恒等式证明恒等式证明(续续)21函数与关系的计数函数与关系的计数22n个球放到个球放到m个盒子的方法计数个盒子的方法计数23