组合数学(第7章7.6).ppt

《组合数学(第7章7.6).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章递推关系和生成函数一个几何例子指数生成函数回顾：递推关系求解与计数递推关系的求解问题常系数线性齐次线性递推关系两种求解方法（1）通过解特征多项式方程求解（2）利用生成函数求解非齐次常系数线性递推关系求解7.6一个几何例子定义1:设有平面或空间中的点集k,若k中任意两点p和q的连线pq上的所有点都在k内,称k是凸集.凸多边形的计数问题n(n3)个顶点的多边形有多少条对角线？连接n个顶点的边数n(n-1)/2对角线数：n(n-1)/2n=n(n-3)/2凸多边形的计数问题凸多边形的n-3条不相交K内（不含边）的对角线将K分成n-2个三角形，存在多少种方法？

2、凸多边形三角形剖分方法计数定理7.6.1通过画出在区域内不相交的对角线,令hn表示具有n+1条边的凸多边形区域分成三角形区域的方法数。定义h1=1。则hn满足如下递推关系:hn=h1hn-1+h2hn-2+…+h1hn-1+hn-1h1=该递推关系解为：证明：（1）求递推关系。验证n=1和n=2时，递推关系成立。令n3,考虑n+1条边的凸多边形区域K。选取K的一条边称为基边，对每一种分法，基边所在的三角形区域将K分成两个部分K1,和K2，其中K1有k+1条边，而K2有n-k+1条边.因此，包含这个三角形的分法有hkhnk种。那么，包含该基边的每一个不同三角形

3、确定了hkhnk种不同的分法。共有hn=K1K2(2)求解（非线性）递推关系。设h1,h2,…,hn…的生成函数g(x)=h1x+h2x2+…+hnxn+…那么，(g(x))2=h12x2+(h1h2+h2h1)x3+…+xn+…注意到h1=h2=1,因此(g(x))2=h12x2+h3x3+…+hnxn+…=h2x2+h3x3+…+hnxn+…=g(x)xg(x)满足方程(g(x))2g(x)+x=0解关于g(x)的方程得到：g1(x)=,g2(x)=由于g(0)=0,而g1(0)=1不符合条件。故根据牛顿二项式定理：代入展开得到：代入得到：因此称为Ca

4、talan数。小结生成函数可用于解决一些特别的递推关系。哪些递推关系适于用生成函数求解？7.7指数生成函数指数函数ex的展开式定义1:序列h0,h1,h2,…,hn,…的指数生成函数定义为:指数生成函数—多重集的排列计数定理7.7.1令S={n1a1,n2a2,…,nkak}为一多重集,其中n1,n2,…,nk均为非负整数.令hn表示S的n-排列数。则序列h0,h1,h2,…,hn,…的指数生成函数g(e)(x)由:g(e)(x)=(7-57)给定。其中，对于i=1,2,…,k(7-58)证明：设序列h0,h1,h2,…,hn,…的指数生成函数是注意到当n

5、n1+n2+…+nk时,hn=0,因此g(e)(x)是有限和。将式子7-58代入7-57，k个因子相乘：其中，0m1n1,0m2n2,…,0mknk。那么，每项形式为：令n=m1+m2+…+mk,则上式可写成：因此，7-57式中xn/n!的系数是：上式对满足n=m1+m2+…+mk和0m1n1,0m2n2,…,0mknk所有整数m1,m2,…,mk求和。我们知道:是S的子多重集{m1a1,m2a2,…,mkak}的排列数.而S的n-排列数等于满足n=m1+m2+…+mk的所有子多重集排列数之和，因此这证明了g(e)(x)是序列h0

6、,h1,h2,…,hn,…的指数生成函数。注意：对于无限重复数情形，定理依然成立。应用例子：限制多重集排列问题hn表示由数字1,2,3组成的n-位数的个数，其中满足1的个数是偶数，2的个数至少是3，3的个数最多是4。确定数列h0,h1,…,hn,…的指数生成函数ge(x)。根据定理7.7.1的推导过程，ge(x)具有3个因子，分别由3个元素1,2,3的限制条件确定。对应1的因子为：对应2的因子为：对应3的因子为：那么序列的指数生成函数是：例子例.如果把棋盘上偶数个方格涂成红色,试确定用红色,白色和蓝色对1行n列棋盘上的方格涂色方法数.解：hn表示着色的方法数，h

7、0=1.那么，hn等于三种元素的（无限）多重集的n-排列数，且红色出现偶数次。因此h0,h1,h2,…,hn,…的指数生成函数是：g(e)(x)=因此,小结指数生成函数可用于一些多重集排列计数问题求解。作业7.8习题第4版：37，40，42