组合数学-三种典型数列二

1、5,4,3,2,1,三种典型数列（二）,Catalan数列,主讲人：段龙方,引例,考虑如下问题： 从平面上(0 ,0)点出发到( n , n)点的除端点外不接触直线 y = x ,且在直线y = x 下方的路径数 g ( n)。,思考： 若在直线Y=X上任取一点(k,k)。,用g(k)表示从(0 ,0)到点( k , k)的除端点外不接触直线 y = x ,且在直线y = x 下方的路径数。 同理，用g(n-k)表示从从点( k , k)到点( n , n)的满足条件的路径数。,(k,k),同时，k的取值：（1 、2 、3 n）,引例,思考： (1) 若每条路径都从点(0 ,0)到点( k ,

2、 k) ,再从点( k , k)到点( n , n)，并满足题目条件。 (2) 取遍k从1到n的所有值。,也即根据加法原理和乘法原理，满足条件的g ( n)可用如下式子表示：,（1）式,此处的g(n)就是Catalan数。,引例,思考： 如上所说，当k取一个特定值，g(k)g(n-k)表示此时从点(0 ,0)到点( k , k) ,再从点( k , k)到点( n , n)的路径个数。这时是不是违反了题目中的条件： “除端点外不接触直线 y = x 且在直线y = x 下方”？,（1）式是g(n)的表达式，现在来求解g(n)。,解：上述路径数可以看成是从(0 ,0)点出发,每一次向上或向右游动

3、一个单位,且在直线 y =x 下方,最终到达点( n , n)的路径数,即为从(1 ,0)出发到达( n , n - 1)点的路径数。,(1,0),(n,n-1),也就是在2 n - 2 次游动中向上和向右游动 n - 1 次,因而可能结果总数为： C( 2 n 2,n 1)。,此时上页的问题？,(k,k),(k,k-1),引例,但C( 2 n 2,n 1)种方案是否全部满足题目条件？,不是，此组合数中包含有接触直线 y = x 的情形,对其中任一条接触对角线的路径。,(0,1),因而从 ( 1 , 0) 点出发到点 ( n , n - 1) 且在 y = x 下方的路径数为：C( 2 n 2

4、,n 1)-C( 2 n 2,n ),(1,0),(n,n-1),可把它从最后离开 y = x 的点A 关于直线y = x 作个反射,即得从(0 , 1)出发经过点 A 到( n , n - 1)的路径数,其总数为：C( 2 n 2,n ),A,引例,3.4.3 Catalan数列,定义： 满足递推关系,的数列称为Catalan数列。这是一个定解问题，其解为：,解：设Catalan数列的母函数为A(x),即,下面用母函数的方法来求解。,那么观察Catalan数列满足的递推关系，我们先来求A2(x).,=(C1C1)x2+(C1C2+C2C1)x3+(C1Cn-1+C2Cn-2+Cn-1C1)x

5、n+,=C2x2 + C3x3 + Cnxn +,+ C1x - C1x,=A(x) - x,3.4.3 Catalan数列,即 A2(2)-A(x)+x=0,解之得,，,由于A(0)=0,故只取,根据二项式定理，参考课本P78计算过程，得到,故,3.4.3 Catalan数列,【例1】 Euler在精确计算使用对角线 对凸n边形进行三角剖分的个数时，最早得到了这个数列。,其问题是：将凸n边形用不相交的对角线分成三角形，有多少中不同的剖分方法？,例如，五边形就有五种剖分方案，如下图。,再如，六边形就有十四种剖分方案，如下页所示。,思考: （1） 凸多边形定义。（不是正多边形） （2） 剖分结果

6、：凸多边形的每一部分都是三角形。,3.4.3 Catalan数列,解：设用对角线 对凸n边形进行三角剖分的方案个数为hn ，显然n3且h3=1,h4=2.那么。当n 3时，设凸n+1边形的顶点一次为v1，v2， ，vn+1，固定一条边v1vn+1, 再另取一个顶点vk(k=2,3,n)，作v1vkvn+1，它分多边形为两个较小的凸多边形，如下图。,一个是凸k边形，其剖分数就是 hk，另一个是n-k+2边形，其剖分数为hn-k+2。由乘法原理和加法原理，当k取遍所有取值即可得到式子（2）：,（2）式,3.4.3 Catalan数列,上式与Catalan数列的递推关系相对比，可知hn=Cn-1.,

7、连接凸n边形的两点v1、vk，将多边形一分为二，对应的剖分数为hkhn-k+2。这时，k=3,4， ，n-1。由加法原理得对应于v1的三角剖分数为h3hn-1+h4hn-2+hn-1h3。,另外要指出，Catalan数列还满足某个一阶变系数的线性递推关系，下面进行推导。,3.4.3 Catalan数列,其中，规定h2=1.,由对称性，对应于其它任一顶点的剖分数也是如此。故在重复运算的情况下得n ( h3hn-1+h4hn-2+hn-1h3 ) 种三角剖分。,因为以上是按顶点统计的，若按对角线来统计，由于每条对角线有两个顶点。因此三角剖分数应为：,但是，这也不是真正剖分数。,此时有重复的剖分方案

8、。,还应该注意到，由于剖分的结果是凸n边形只能由三角形组成，故对于某一种剖分方案，要用n-3条对角线来形成。,3.4.3 Catalan数列,不同的剖分方案只是改变了该n-3条对角线的“布局”。 即同一种剖分方案，若按对角线来统计，则被计算了n-3 次。因此有：,由（2）式得hn+1-2hn=h3hn-1+h4hn-2+hn-1h3，与上式比较，得,整理得,3.4.3 Catalan数列,【例2】设P=a1a2.an为n个数的连乘积，保持原来的排列顺序，试问有多少种不同的结合方案（即根据乘法的结合律插入n-1对括号，使得每对括号内为恰好是两个因子的乘积.如n=4，P=(a1a2)(a3a4)=

9、(a1(a2a3)a4)=.？,解：设pn为插入n-1对括号的方案数。对于a1a2.an的每一种结合方案，其最后的那次乘法运算必是a1a2.ak的相乘结果P1和ak+1.an的相乘结果P2两项相乘 ( 1kn-1 ) ，即最外层括号所含的两个因子P1和P2 .对于固定的k，P1有pk种不容的组合方案，P2则有pn-k种.,3.4.3 Catalan数列,P=( (a1.ak) (ak+1.an) ),显然，,类似的问题还有：在n项求和式中，不改变各数的相对排列次序，只给其插入括号改变求和顺序，不同的结合方案数也是Cn。,事实上，n个数连乘积的结合方案与凸n+1边形的三角剖分是一一对应的，参见课

10、本P81页图3.4.5。,3.4.3 Catalan数列,因此，总的方案数是：,【例3】求具有n个结点的二叉树的个数.即具有n个结点的所 有结构上不同的二叉树有多少个？,解：令bn表示n个结点的二叉树总数，容易看出，b0=b1=1.含有三个结点的所有不同的二叉树如下图所示。,3.4.3 Catalan数列,1）对于一般情形，二叉树有一个根结点及n-1个非根结点，后者又可分为两个子集，分别构成左子树和右子树。,2）设左子树有k个结点，则右子树有n-1-k个结点。于是作为根的左子树的所有可能的二叉树的数目是bk，作为根的右子树的所有可能的二叉树的数目是bn-1-k (k=0,1,n-1) 。,因此

11、，由乘法原理和加法原理便知,3.4.3 Catalan数列,令bn=rn+1 (n=0,1,2,) ,得数列rn满足的递推关系,即,由上式可知，rn=Cn. 所以，所求二叉树的个数为：,3.4.3 Catalan数列,【例4】证明有n个结点的所有不同的有序树的个数时Cn。 解：,（1）任何一个有序树都可用二叉树表示。 （2）对应于有序树的二叉树的右子树是空二叉树。,故具有n个结点的有序树和具有n-1个结点的二叉树之间存在一一对应的关系。因此，有n个结点的有序树的个数为bn-1，即Cn。,有序树与二叉树对应示例,3.4.3 Catalan数列,以上我们讲了Catalan数列的多种问题模型。包括 （0,0）到（n,n）的路径数模型； 凸多边形的三角剖分方案模型； 括号分隔n个数的连乘积的模型； n个结点的不同二叉树模型； n个结点的不同有序树模型。,经典Catalan 数具有许多组合应用背景, 除了几何、