组合数学(第7章7.6)[精选].ppt

第七章 递推关系和生成函数 一个几何例子 指数生成函数 回顾：递推关系求解与计数 递推关系的求解问题 常系数线性齐次线性递推关系两种求解方法 （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个三角形，存在多少种方法？ 凸多边形三角形剖分方法计数 定理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种。 那么，包含该基边的每一个不同三角形确定了hkhn?k种不同的分法。 共有 (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)?x g(x)满足方程 (g(x))2?g(x)+x=0 解关于g(x)的方程得到： g1(x)= , g2(x)= 由于g(0)=0, 而g1(0)=1不符合条件。故 代入展开得到： 小结 生成函数可用于解决一些特别的递推关系。 哪些递推关系适于用生成函数求解？ 7.7 指数生成函数 指数函数ex的展开式 指数生成函数—多重集的排列计数 定理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 证明：设序列h0,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的因子为： 例子 例. 如果把棋盘上偶数个方格涂成红色, 试确定用红色,白色和蓝色对1行n列棋盘上的方格涂色方法数. 解：hn表示着色的方法数，h0=1. 那么，hn等于三种元素的（无限）多重集的n-排列数，且红色出现偶数次。因此h0,h1,h2,…, hn,…的指数生成函数是： 小结 指数生成函数可用于一些多重集排列计数问题求解。 作业 7.8习题 第4版：37，40，42 * * hn= K1 K2 根据牛顿二项式定理： 代入得到： 因此 称为Catalan数。 定义1: 序列h0,h1,h2,…,hn,…的指数生成函数定义为: (7-58) 注意到当n?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求和。 我们知道: