Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。
问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如下五种拆分方案(图6-4)，故h5=5。求对于一个任意的凸n边形相应的hn。
图3
解：设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1 Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，??，Pn-1点中找一个点Pk(1 其中区域③必定是一个三角形，区域①是一个凸k边 形，区域②是一个凸n-k+1边形，区域①的拆分方案P2 P3 总数是Ck，区域②的拆分方案数为Cn-k+1，故包含△P1PkPn ① 的n 边形的拆分方案数为CkCn-k+1种，而Pk可以是P2，Pk P1 P3，??，Pn-1种任一点，根据加法原理，凸n边形的③ Pn ② Pn--1 三角拆分方案总数为?CiCn?i?1，同时考虑到计算的方 i?2n?1图4 便，约定边界条件C2=1。 小结：通过上面对四种典型的递推关系建立过程的探讨，可知对待递推 类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。 例题精讲 例1、在一个正六边形的六个区域中的每一个 区域染上红、黄、蓝、紫四种颜色之一，要求相邻的 两个区域染色不相同，则有多少种不同的染色方法？ FE【分析】本问题属于排列组合方面的问题。 用心 爱心 专心 ADBC EE、、CC、、AA 思路一：利用排列组合的知识进行求解，由于图形的特殊性，可以按 A、C、E染色情况进行分类。 思路二：将该图形抽象出来，形成一般的问题：“将圆分为n(n?2)个扇形，每个扇形区域染上红、黄、蓝、紫四种颜色之一，要求相邻的扇形区域染色不相同，问有多少种染色方法？”先求通项an或递推关系，再求a6。 【解答】解法一：按A、C、E染色情况进行分类： （1）若A、C、E染一种色，则此时共有4?3?3?3?108种方法； （2）若A、C、E染三种色，则此时共有P43?2?2?2?192种方法； （3）若 2染二种色，则此时共有P42?C3?3?2?2?432种。 故总计共有108+192+432=732种方法。 解法二：将问题抽象成一般问题：“将圆分为n(n?2)个扇形，每个扇形区域染上红、黄、蓝、紫四种颜色之一，要求相邻的扇形区域染色不相同，记染色方法总数为an，求a6”。 ?an?an?1?4?3n?1(n?3)由已知条件容易建立递推关系?。 a?12?2由该递推关系易求出a3?24,a4?84,a5?240,a6?732。 【评注】（1）解法一中若不按A、C、E染色情况进行分类可能比较复杂， 并且当染二种色时，计算染法数比较容易出错； （2）解法二中关键之处在于建立递推式子，但递推式子建立后计算比 较方便。 例2有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。 ?? 3 4 5 6 7 8 9 11 13 10 12 14 ?? 图6 解：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b点的路径只能是从b-1点或b-2点到达的，故fn=fn-1+fn-2 (a+2?n?b)，边界条件fa=1，fa+1=1。 附程序： 用心 爱心 专心 program Pro_1;{蜂巢问题，最大范围：目标点与出发点之差不超过40000} type Tarr=array[1..10000] of byte; Tnum=array[1..4] of ^Tarr; Tlen=array[1..4] of word; var start,finish:longint; {出发点和目标点} num:Tnum; {num[1]?num[3]分别保存到达相邻三个蜂巢的路径数；num[4]是用于交换的临时变量} len:Tlen; {len[i]表示num[i]的长度} procedure DataInit;{数据初始化} var i:integer; begin for i:=1 to 3 do begin new(num[i]); fillchar(num[i]^,sizeof(num[i]^),0); num[i]^[1]:=1; len[i]:=1; end; end; procedure Add;{高精度加法运算：num[3]=num[1]+num[2]} var i,carry:word;{carry是进位数字} begin carry:=0; for i:=1 to len[2] do begin carry:=carry+num[2]^[i]+num[1]^[i]; num[3]^[i]:=carry mod 10; carry:=carry div 10; end; len[3]:=i; if carry>0 then begin inc(len[3]); num[3]^[i+1]:=carry; end; end; 用心 爱心 专心 procedure Work;{求从出发点到目标点的路径总数} var i:longint; begin num[1]^[1]:=1; num[2]^[1]:=1; for i:=start+2 to finish do begin Add;{高精度加法运算：num[3]=num[1]+num[2]} num[4]:=num[1]; num[1]:=num[2]; num[2]:=num[3]; num[3]:=num[4]; len[4]:=len[1]; move(len[2],len[1],6); end; end; procedure Out;{输出结果} var i:integer; begin for i:=len[2] downto 1 do write(num[2]^[i]); writeln; end; begin DataInit; {数据初始化} write('Input: '); readln(start,finish); Work; {求从出发点到目标点的路径总数} Out; {输出结果} end. 练习： 第1题(5分)，有5本不同的数学书分给5个男同学，有4本不同的英 语书分给4个女同学，将全部书收回来后再从新发给他们，与原方案都不相同的方案有________种。 答案： 5!*4!+D(5)*D(4)=1140480 其中：D(n)=(n-1)*(D(n-1)+D(n-2)) (n > 2) D(1)=0 D(2)=1 用心 爱心 专心 第2题(5分)，在m*n的棋盘上，每个方格(单位正方形，即边长为1 的正方形)的顶点称为格点。以格点为顶点的多边形称为格点多边形。若设格点凸N边形面积的最小值为gn，格点凸N边形内部(非顶点的)格点的个数的最小值为fn，则gn和fn的关系式为gn=___________。 答案： Gn= fn+N/2-1 ( N >= 3 ) 第3题(8分)，有位小同学喜欢在方阵中填数字，规则是按下图示例从 右上角开始，按斜线填数字，碰到边界就重新。显然，数字1在坐标(1，5)位置，数字25在坐标(5，1)位置。后来这位小朋友想知道，对于N阶的方阵，随机取一个位置(x，y)，并规定x≤y，问这个位置上应该填的数字是多少?5阶方阵的 示例图如下： 11 7 4 2 1 16 12 8 5 3 20 17 13 9 6 23 21 18 14 10 25 24 22 19 15 答案： (N-y+x)*(N-y+x-1)/2+x 第4题(5分)，把三角形各边分成n等分，过每一分点分别做各边的平 行线，得到一些由三角形的边和这些平行线所组成的平行四边形。n为已知整数，能组成_______个平行四边形。 答案： 3*C(n+2,4) 第5题(5分)，由a，b，c3个不同的数字组成一个N位数，要求不出 现两个a相邻，也不出现两个b相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为：AN＝_______________。 答案： AN= 2*AN-1+AN-2 用心 爱心 专心 作者单位：江苏省洪泽县第二中学 姓 名：吴斌 通讯地址：江苏省洪泽县第二中学电教中心组 邮编： 223100 电 话：13912054539 QQ:372836808 邮件地址：HZEZDJZX@126.COM 用心 爱心 专心