组合数学 catlan数

1、2.11 Catalan,数,这一节讨论,Catalan,数,其递推关系是非,线性的,许多有意义的计数问题都导致这样,的递推关系,本节将举出一些,后面还将见到,一个凸,n,边形,通过不相交于,n,边形的对角,线,把,n,边形拆分成若干三角形,不同拆分的,数目用,表之,n,h,2.11 Catalan,数,例如五边形有如下五种拆分方案，故,5,n,h,图,2-11-1,2.11 Catalan,数,1,递推关系,定理,2,11,2,2,3,1,11,2,3,1,4,2,2,4,1,3,2,1,3,2,1,h,h,h,h,h,h,h,h,n,h,n,b,h,h,h,h,h,h,h,a,n,n,n,

2、n,n,n,n,n,n,2.11 Catalan,数,证明,的证明,如图,所示,以,作为一个边,的三角形,将凸,边形分割,成两部分，一部分是,边形,1,v,2,v,3,v,k,v,n,v,1,n,v,边形,k,边形,2,k,n,图,2-11-2,a,1,11,2,1,1,n,v,v,1,n,1,1,n,k,v,v,v,k,2.11 Catalan,数,另一部分是,边形,即,点可以是,点中任意一点。依据加,法法则有,2,k,n,3,2,n,k,k,v,n,v,v,v,3,2,2,3,1,1,3,2,2,2,1,h,h,h,h,h,h,h,h,h,h,h,n,n,n,n,n,k,k,n,k,n,2

3、.11 Catalan,数,的证明,如图,所示,从,点向其它,个,顶点,可引出,条对角线,对角线,把,边形,分割成两个部分，因此,1,v,2,v,k,v,n,v,边形,k,边形,2,k,n,图,2-11-3,b,3,11,2,1,v,3,n,1,4,3,n,v,v,v,k,v,v,1,3,n,n,2.11 Catalan,数,以,对角线作为拆分线的方案数为,可以是,中任一点，对所有这,些点求和得,以,取代,点也有类似的结果。但,考虑到对角线有两个顶点，同一对角线在两,个顶点分别计算了一次,k,v,v,1,2,k,n,k,h,h,k,v,1,4,3,n,v,v,v,3,1,4,2,2,4,1,3

4、,h,h,h,h,h,h,h,h,n,n,n,n,n,v,v,v,3,2,1,v,2.11 Catalan,数,作,3,11,2,2,3,1,4,2,2,4,1,3,h,h,h,h,h,h,h,h,n,n,n,n,n,式并不就给出剖分数，无疑其中,是有重复的。其重复度是由于一个凸,边形,的剖分有,条对角线，而对其每一条边,计数时该剖分都计数了一次，故重复了,次即,式给出的结果是,的,倍,3,11,2,3,n,3,n,n,3,11,2,n,h,3,n,2.11 Catalan,数,式和,式都是非线性的,递推关系,2,3,3,1,4,2,2,4,1,3,h,h,h,h,h,h,h,h,n,h,n,

5、n,n,n,n,n,1,11,2,2,11,2,2.11 Catalan,数,2.Catalan,数计算公式,由,式及,故得,1,11,2,1,2,h,2,2,2,3,2,1,3,1,2,4,1,3,3,1,4,2,2,4,1,3,1,n,n,n,n,n,n,n,n,n,n,n,n,h,h,n,h,h,h,h,h,h,n,h,n,h,h,h,h,h,h,h,h,h,h,2.11 Catalan,数,由,整理得,令,2,2,3,1,n,n,n,h,h,n,h,n,2,3,2,1,n,n,n,nh,nh,h,n,6,4,1,n,n,h,n,nh,1,1,n,n,nh,f,1,1,3,2,2,2,1

6、,3,2,1,6,4,1,n,n,n,n,f,n,n,n,n,f,n,n,n,f,n,f,2.11 Catalan,数,即,1,1,1,3,2,2,2,2,2,1,h,f,n,n,n,n,f,f,n,n,1,1,2,2,2,2,3,4,2,2,5,2,4,2,1,1,3,2,2,2,2,3,3,4,2,1,1,1,1,n,n,n,n,n,n,n,n,f,f,f,f,f,f,f,f,f,f,f,n,n,n,n,n,n,n,2.11 Catalan,数,1,2,2,1,1,2,2,1,1,2,2,1,1,n,n,n,h,nb,n,n,n,n,n,n,n,2.11 Catalan,数,例,1.,见图

7、,例,2,为,n,个数,的乘积,依据乘法的结合率,不改变其顺序,只用括号表示成对的乘积,试问有几种不同,的乘法方案,14,4,8,5,1,6,h,4,11,2,n,a,a,a,a,P,3,2,1,n,a,a,a,2,1,2.11 Catalan,数,令,表示,n,个数乘积的,对括号插入的不,同方案数,令,故得,而且,故,即为,Catalan,数,n,p,1,n,1,2,1,1,1,2,2,1,1,p,p,p,p,p,p,p,p,p,n,n,n,n,3,2,1,1,n,k,p,p,k,k,2,3,1,1,3,2,1,h,h,h,h,h,h,h,h,h,n,n,n,n,n,1,1,1,n,n,h,

8、h,n,p,1,n,h,2.11 Catalan,数,以,为例,4,n,5,3,6,4,1,5,4,h,p,4,11,2,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,Catalan,数,下面建立,式,中不同的乘法顺序和一个,5,边形不同拆分的,一一对应关系，如图,6,11,2,4,p,5,h,4,11,2,2.11 Catalan,数,2,a,4,3,2,1,a,a,a,a,1,a,2,a,3,a,4,a,0,a,1,a,3,a,4,a,3,2,1,a,a,a,3,2,a,a,4

9、,3,2,1,a,a,a,a,1,a,2,a,3,a,4,a,0,a,1,a,2,a,3,a,4,a,3,2,1,a,a,a,2,1,a,a,2.11 Catalan,数,4,3,2,1,a,a,a,a,1,a,2,a,3,a,4,a,0,a,1,a,2,a,3,a,4,a,2,1,a,a,4,3,a,a,4,3,2,1,a,a,a,a,1,a,2,a,3,a,4,a,0,a,1,a,2,a,3,a,4,a,4,3,2,a,a,a,4,3,a,a,2.11 Catalan,数,4,3,2,1,a,a,a,a,1,a,2,a,3,a,4,a,0,a,1,a,2,a,3,a,4,a,4,3,2,a

10、,a,a,3,2,a,a,图,2-11-6,2.11 Catalan,数,运算用二分树表示，两片叶子分别表,乘数和被乘数，分支点为运,算符,如图,b,a,a,b,图,2-11-5,b,a,5,11,2,2.11 Catalan,数,例,3,n,个,1,和,n,个,0,组成一,2n,位的,2,进制数，要,求从左到右扫描,1,的累计数不小于,0,的累计,数，试求满足这条件的数有多少,下面介绍两种算法,解法,1,设,为这样所得的数的个数。在,2n,位上填入,n,个,1,的方案数为,不填,1,的其余,n,p,2,n,n,2,2.11 Catalan,数,n,位自动填以数,0,从,中减去不符合要求,的方

11、案数即为所求。不合要求的数指的是从,左而右扫描，出现,0,的累计数超过,1,的累计数,的数,不合要求的数的特征是从左而右扫描时,必然在某一奇数,位上首先出现,n,n,2,1,2,m,1,m,2.11 Catalan,数,个,0,的累计数，和,m,个,1,的累计数,此后的,位上有,个,1,个,0,如若把后面这部分,位,0,与,1,交换，使之成为,个,0,个,1,结果得,1,个由,个,0,和,个,1,组成,的,2n,位数，即一个不合要求的数对应于一个,由,个,0,和,个,1,组成的一个排列,1,2,m,n,m,n,1,m,n,1,2,m,n,m,n,1,m,n,1,n,1,n,1,n,1,n,2.

12、11 Catalan,数,反过来，任何一个由,个,0,个,1,组,成的,2n,位数，由于,0,的个数多,2,个,2n,是偶数,故必在某一个奇数位上出现,0,的累计数超过,1,的累计数。同样在后面的部分，令,0,和,1,互换,使之成为由,n,个,0,和,n,个,1,组成的,2n,位数。即,个,0,和,个,1,组成的,2n,位数，必对应于一个,不合要求的数,1,n,1,n,1,n,1,n,2.11 Catalan,数,用上述方法建立了由,个,0,和,个,1,组成的,2n,位数，与由,n,个,0,和,n,个,1,组成的,2n,位,数中从左向右扫描出现,0,的累计数超过,1,的累,计数的数一一对应,例

13、如,是由,4,个,0,和,4,个,1,组成的,8,位,2,进制数。但从左而右扫描在第,5,位（打,号,出现,0,的累计数,3,超过,1,的累计数,2,它对应于,1,n,1,n,10100101,2.11 Catalan,数,由,3,个,1,5,个,0,组成的,10100010,反过来,对应于,因而不合要求的,2n,位数与,个,0,个,1,组成的排列一一对应，故有,10100010,10100101,1,n,1,n,1,1,1,1,2,1,2,2,2,n,n,n,n,n,n,n,n,n,p,n,2.11 Catalan,数,2,1,1,1,2,1,1,1,2,n,n,n,n,n,n,n,n,n,n,n,n,n,2.11 Catalan,数,例,4,由,n,个,1,n,个,0,组成的,2n,位二进制数,要,求从左向右扫描前,位时,1,的累计数大于,0,的累计数，求满足这样条件的数的个数。此,问题可归结为图,中从,点出发只经过,对角线,上方的点抵达,点，求这样的路径,数。相当于求从,点不经过对角线,抵达,点的路径数，于是便转换为