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

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

ID:39884204

大小:342.50 KB

页数:23页

时间:2019-07-14

离散数学--103-4指数生成函数及其应用_第1页
离散数学--103-4指数生成函数及其应用_第2页
离散数学--103-4指数生成函数及其应用_第3页
离散数学--103-4指数生成函数及其应用_第4页
离散数学--103-4指数生成函数及其应用_第5页
资源描述:

《离散数学--103-4指数生成函数及其应用》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、指数生成函数的定义与实例指数生成函数的性质指数生成函数的应用10.3指数生成函数及其应用1课件指数生成函数的定义与实例例1给定正整数m,an=P(m,n),{an}的指数生成函数为例2bn=1,则{bn}的指数生成函数为定义10.7设{an}为序列,称为{an}的指数生成函数.2课件指数生成函数的性质设数列{an},{bn}的指数生成函数分别为Ae(x)和Be(x),则其中证3课件指数生成函数的应用——多重集排列计数定理10.8设S={n1a1,n2a2,…,nkak}为多重集,则S的r排列数的指数生成函数

2、为4课件证明考察指数生成函数展开式中xr的项其中m1+m2+…+mk=r0mini,i=1,2,…,k(*)其中求和是对满足方程(*)的一切非负整数解来求.一个非负整数解对应了{m1a1,m2a2,…,mkak},即S的r组合而该组合的全排列数是,ar是S的r排列数.5课件实例例3由1,2,3,4组成的五位数中,要求1出现不超过2次,但不能不出现,2出现不超过1次,3出现可达3次,4出现偶数次.求这样的五位数个数.解N=2156课件实例(续)例4红、白、兰涂色1n的方格,要求偶数个为白色,问有多少方案

3、?解设方案数为an7课件10.4Catalan数与Stirling数Catalan数第一类Stirling数第二类Stirling数8课件Catalan数的定义定义10.8一个凸n+1边形,通过不相交于n+1边形内部的对角线把n+1边形划分成三角形,划分方案个数记作hn,称为Catalan数.实例:h4=5初值h2=19课件Catalan数的递推方程考虑n+1条边的多边形,端点A1,An+1的边记为a,对于任意的k=1,2,…,n1,以Ak+1A1为边,An+1Ak+1为另一边,与a构成三角形T,T将多边形划分

4、成R1和R2两个部分,分别为k+1边形和nk+1边形.递推方程10课件Catalan数对应的组合问题从(0,0)到(n,n)的除了端点以外不接触对角线的非降路径数2hna1a2…an,不改变因子顺序,加括号的方法数hnn片树叶的有序三度根树个数hn2n个点均匀分布在圆周上,用n条不相交的弦配对的方法数hn+1n个数的堆栈的不同输出个数hn+111课件实例——计数堆栈的输出个数例11,2,…,n放入堆栈后的不同的输出个数解在1进栈到出栈之间作为一个子问题,1出栈后作为一个子问题.过程如下:步2:子问题规模k

5、,步4:子问题规模nk11.1进栈;2.处理k个数(2,…,k+1)的进栈问题;3.1出栈;4.处理k+2,…,n的进栈问题;12课件计数堆栈的输出个数(续)13课件第一类Stirling数将xr系数的绝对值Sr记作,称为第一类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xx(x1)(x2)=x33x2+2x14课件第一类Stirling数的递推方程15课件第一类Stir

6、ling数的恒等式16课件第二类Stirling数的定义17课件第二类Stirling数的递推方程18课件第二类Stirling数的恒等式19课件恒等式证明20课件恒等式证明(续)21课件函数与关系的计数22课件n个球放到m个盒子的方法计数23课件

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。