《离散数学》课件 第22章 组合计数方法.ppt

*************************************************************对应组合问题:函数关系计数*小结鸽巢原理的一般形式及应用加法法则与乘法法则，分类处理与分步处理递推方程的求解方法（公式法、迭代归纳法、生成函数法）及应用生成函数、指数生成函数及应用组合计数模型选取模型、非降路径、方程非负整数解、整数拆分、放球组合数一般计数：P(n,k)、C(n,k)、多项式系数Fibonacci数fn、错位排列数DnCatalan数、两类Stirling数以上计数的定义、组合含义、恒等式证明方法*******************************无序拆分*实例*有限制条件的无序拆分将N无序拆分成正整数a1,a2,…,ana1x1+a2x2+…+anxn=N限制条件：li?xi?ti,转变为方程非负整数解的问题*有限制条件的无序拆分*大小k个数k有序拆分*有序拆分(续)方法二：生成函数.G(y)=(y+y2+y3+…)r中yN项的系数.所求的方法数为(2)不允许重复有序拆分：不允许重复无序拆分+全排列*22.5指数生成函数*指数生成函数的性质*应用-多重集排列计数*证明*实例*应用(生成函数求法)*22.6高级计数高级计数Catalan数第一类Stirling数第二类Stirling数讨论要点定义递推方程恒等式对应的组合问题生成函数*Catalan数定义定义一个凸n+1边形，通过不相交于n+1边形内部的对角线把n+1边形拆分成的三角形个数，记作hn，称为Catalan数.实例：h2=1,h3=2,h4=5*递推方程*生成函数及对应的组合问题*矩阵乘法：设A1,A2,…,An为矩阵序列，Ai为Pi-1?Pi阶矩阵，i=1,2,…,n.确定乘法顺序使得元素相乘的总次数最少.输入：向量P=P0,P1,…,Pn实例：P=10,100,5,50A1:10?100,A2:100?5,A3:5?50,(A1A2)A3:10?100?5+10?5?50=7500A1(A2A3):10?100?50+100?5?50=75000应用：有哪些信誉好的足球投注网站规模的估计*一般算法：n-1次运算加括号方法有种，Stirling公式方法数应用:栈的输出计数*栈的输出个数(续)*第一类Stirling数*递推方程*递推三角形*11123611612450351011n=1n=2n=3n=4n=5r=1r=2r=3r=4r=5恒等式及生成函数*(3)式的证明*第二类Stirling数*递推方程*111136761115251011n=1n=2n=3n=4n=5r=1r=2r=3r=4r=5恒等式*恒等式证明*恒等式证明(续)*生成函数*