1、2.11 2.11 Catalan Catalan 数数 这一节讨论Catalan数,其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.本节将举出一些,后面还将见到.一个凸n边形,通过不相交于n边形的对角线,把n边形拆分成若干三角形,不同拆分的数目用 表之.nh2.11 2.11 Catalan Catalan 数数例如五边形有如下五种拆分方案，故.5nh图 2-11-12.11 2.11 Catalan Catalan 数数1.1.递推关系递推关系定理：定理：)2112().(2)3()()1112(,)(3142241321321hhhhhhhhnhnbhhhhhhhannn
2、nnnnnn2.11 2.11 Catalan Catalan 数数证明：证明：的证明：如图 所示，以 作为一个边的三角形 ，将凸 边形分割成两部分，一部分是 边形，1v2v3vkvnv1nv边形k边形2kn图 2-11-2)(a111211nvv1n11nkvvvk2.11 2.11 Catalan Catalan 数数另一部分是 边形，即点可以是 点中任意一点。依据加法法则有2kn,3,2nkkvnvvv,32.231132221hhhhhhhhhhhnnnnnkknkn2.11 2.11 Catalan Catalan 数数 的证明：如图 所示，从 点向其它 个顶点可引出 条对角线。对角
3、线 把 边形分割成两个部分，因此1v2vkvnv边形k边形2kn图 2-11-3)(b31121v3n,143nvvvkvv13nn2.11 2.11 Catalan Catalan 数数以 对角线作为拆分线的方案数为 可以是 中任一点，对所有这些点求和得以 取代 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，kvv12knkhhkv143,nvvv.31422413hhhhhhhhnnnnnvvv,321v2.11 2.11 Catalan Catalan 数数作)3112(),(231422413hhhhhhhhnnnnn 式并不就给出剖分数，无疑其中是有
4、重复的。其重复度是由于一个凸 边形的剖分有 条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了次即 式给出的结果是 的 倍。)3112(3n3nn3112nh3n2.11 2.11 Catalan Catalan 数数 式和 式都是非线性的递推关系。).(2)3(31422413hhhhhhhhnhnnnnnn)1112()2112(2.11 2.11 Catalan Catalan 数数2.2.Catalan Catalan 数计算公式数计算公式由 式及 ,故得)1112(12h)2(2 )(2)3(.21312413314224131nnnnnnnnnnnnhhnhhhhhhnhn
5、hhhhhhhhhh2.11 2.11 Catalan Catalan 数数由整理得令),2(2)3(1nnnhhnhn.2)3(21nnnnhnhhn.)64(1nnhnnh,11nnnhf.)1)(1()32)(22(1)3(21)64(1nnnnfnnnnfnnnfnf2.11 2.11 Catalan Catalan 数数即,1,)1)(1()32)(22(221hfnnnnffnn11222234 )2)(2()52)(42()1)(1()32)(22(233421111nnnnnnnnfffffffffffnnnnnnn2.11 2.11 Catalan Catalan 数数.12
6、21 .122)!1()!1()!22(11nnnhnbnnnnnnn2.11 2.11 Catalan Catalan 数数例例1.,1.,见图例例2.2.为n个数的乘积,依据乘法的结合率,不改变其顺序,只用括号表示成对的乘积.试问有几种不同的乘法方案?1448516h4112naaaaP321naaa,212.11 2.11 Catalan Catalan 数数令 表示n个数乘积的 对括号插入的不同方案数.令 故得而且 故 即为Catalan数np1n.1,21112211pppppppppnnnn,3,2,1,1nkppkk,2311321hhhhhhhhhnnnnn.111nnhhnp
7、.1nh2.11 2.11 Catalan Catalan 数数以 为例4n.5364154 hp4)-11-(2 ).)(),(),)(),)(),)(43214321432143214321aaaaaaaaaaaaaaaaaaaa Catalan数 ，下面建立 式中不同的乘法顺序和一个5边形不同拆分的一一对应关系，如图61124p5h4)-11-(22.11 2.11 Catalan Catalan 数数2a)(4321aaaa1a2a3a4a0a1a3a4a)(321aaa)(32aa)(4321aaaa1a2a3a4a0a1a2a3a4a)(321aaa)(21aa2.11 2.11
8、Catalan Catalan 数数)(4321aaaa1a2a3a4a0a1a2a3a4a)(21aa)(43aa)(4321aaaa1a2a3a4a0a1a2a3a4a)(432aaa)(43aa2.11 2.11 Catalan Catalan 数数)(4321aaaa1a2a3a4a0a1a2a3a4a)(432aaa)(32aa图 2-11-62.11 2.11 Catalan Catalan 数数 运算用二分树表示，两片叶子分别表乘数和被乘数，分支点为运算符 ，如图)(baab图 2-11-5ba51122.11 2.11 Catalan Catalan 数数例例3.3.n个1和n
9、个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？下面介绍两种算法。解法解法1.1.设 为这样所得的数的个数。在2n位上填入n个1的方案数为 ，不填1的其余np2nn22.11 2.11 Catalan Catalan 数数n位自动填以数0。从 中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。不合要求的数的特征是从左而右扫描时，必然在某一奇数 位上首先出现nn212m1m2.11 2.11 Catalan Catalan 数数个0的累计数，和m个1的累计数。此后的 位上有 个1，个0。如若把后
10、面这部分 位，0与1交换，使之成为 个0，个1，结果得1个由 个0和 个1组成的2n位数，即一个不合要求的数对应于一个由 个0和 个1组成的一个排列。1)(2mnmn1mn1)(2mnmn1mn1n1n1n1n2.11 2.11 Catalan Catalan 数数 反过来，任何一个由 个0，个1组成的2n位数，由于0的个数多2个，2n是偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面的部分，令0和1互换，使之成为由n个0和n个1组成的2n位数。即个0和 个1组成的2n位数，必对应于一个不合要求的数。1n1n1n1n2.11 2.11 Catalan Catalan 数数 用
11、上述方法建立了由 个0和 个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。例如 是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位（打*号）出现0的累计数3超过1的累计数2，它对应于1n1n*101001012.11 2.11 Catalan Catalan 数数由3个1，5个0组成的 。10100010 反过来 对应于 。因而不合要求的2n位数与 个0，个1组成的排列一一对应，故有*10100010101001011n1n)!1()!1(1!1)!2(1222nnnnnnnnnpn2.11 2.11 Catalan Cat
12、alan 数数.211!)!1()!2(!)!1(!)!1(1)!2(nnnnnnnnnnnnn2.11 2.11 Catalan Catalan 数数例例4.4.由n个1，n个0组成的2n位二进制数，要求从左向右扫描前 位时1的累计数大于0的累计数，求满足这样条件的数的个数。此问题可归结为图 中从 点出发只经过对角线 上方的点抵达 点，求这样的路径数。相当于求从 点不经过对角线 ，抵达 点的路径数，于是便转换为12 n7112OOAA)1,0(OOA),1(nnA2.11 2.11 Catalan Catalan 数数例3的问题。根据例3的结果。从 点通过 的点，以及 上方的点到达 的路径数为)1,0(OAOAO),1(nnA)!1(!1)!22()!2(!1 )!1()!1(1)!22(22122nnnnnnnnnnnnnn2.11 2.11 Catalan Catalan 数数.12211nhnnn
