Catalan数在算法分析中的应用

摘要：如果一个问题其数学模型与Catalan数的递推公式相符合,就可以利用Catalan数的某些结论来解决此问题。可使看上去比较复杂的问题的解决变得比较容易。有些算法的分析可能比较复杂,也可以利用组合数学的某些结论来进行分析。

关键词：Catalan数；算法；算法效率；组合数学

中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2010) 15-0000-01

The Use of Catalan in the Algorithm Analysis

Yang Wenzhong1,Hao Zimian2

(1.Xinjiang Institute of Information Science&Engineering,Xinjiang830046,China;2.Hubei Urban Construction Vocational&Technological College,Wuhan430205)

Abstract:If a problem their mathematical model and the recursive formula for Catalan numbers match,you can use some of the conclusions Catalan numbers to solve this problem.Can seem more complex problems becomes easier.Some may be more complex analysis algorithms,combinatorial mathematics can also be used to analyze some of the conclusions.

Keywords:Catalan number;Algorithm;Algorithm efficiency;Combinatorics

一、Catalan计数序列及其递推公式

（一）Catalan数

Catalan数即序列C0,C1,C2,…,Cn,…。其中Cn= (n=0,1,2,…)。前几个Catalan数为C0=1,C1=1,C2=2,C3=5,C4=14,C5=42,C6=132,C7=429,C8=1430,C9=4862。

（二）递推公式

公式1：Cn=C0Cn-1+C1Cn-2+…+Cn-1C0=(1)

此公式为Catalan数最常见递推公式。由公式可得出Cn=(n=0,1,2,…),其证明过程主要是求此非线性递推公式的生成函数, 具体证明可参见参考文献中的组合数学。

公式2：Cn= Cn-1 (n≥1) C0=1,C1=1 (2)

此公式也为Catalan数常见递推公式之一。 由公式也可得出Cn=(n=0,1,2,…),其证明过程较为简单。只要不断地递归到C0=1即可。

定理1：n个+1和n个-1构成的2n项a1,a2,…,a2n,其部分和满足a1+a2+…+ak≥0 (k=1,2,…,2n)的数列个数等于第n个Catalan数，即Cn= 。

证明：此定理的可以直接利用排列组合来证明，具体的证明可参见参考文献中的组合数学。这里给出另一种证明方式。

设满足部分和非负的数列个数为Cn，此数列中的每一个都可看成是由i个+1和i个-1以及n-i个+1和n-i个-1这样两个数列构成。 由i个+1和i个-1构成的数列个数为Ci, 由n-i个+1和n-i个-1构成的数列个数为Cn-i，由乘法和加法原理可知Cn= 且C0=1即满足公式1,所以Cn= 。

二、Catalan数的应用

如果一个问题所抽象出的数学模型满足Catalan数的公式1或公式2或符合定理1,则此问题解决方法就有可能直接利用Catalan数的已有结论。

（一）多边形刨分问题

凸n边形通过不相交于其内部的对角线拆分为若干三角形。则不同的拆分方式有多少种?

算法1：设不同的拆分数用hn表示且h2=1。由图1可知hn+1= =h2hn+h3hn-1+…+hn-1h3+hnh2，与公式1比较可知hn+1=Cn-1= 。

因而只需根据公式1计算出Cn, 计算函数如下。

long Catalan(int n)

{int i,j;

long c[20]={1};

for(i=1;i<=n;i++)

for(j=0;j

c[i]=c[i]+c[j]*c[i-j-1]; //此循环为计算Cn=

return c[n]; // c[n]即为Cn

}

算法的时间复杂度为O(n2),空间复杂度为O(n)。

算法2：由图2可知以v1vk为对角线将凸n边形分为一个k边形和一个n-k+2边形。以v1vk为对角线的拆分方案数为hkhn-k+2, vk可以是v3,v4, …,vn-1中一点。则h3hn-1+h4hn-2+…+hn-2h4+hn-1h3表示以v1vk(k=3,4, …,n-1)为对角线的拆分方案数为对角线的拆分方案数总和。

以v2,v3, …,vn取代v1也有类似结果。又由于一条对角线的两个端点分别计算了一次,作n(h3hn-1+h4hn-2+…+hn-2h4+hn-1h3)/2式子,但此式子有重复,重复度是由于一个凸n边形的拆分有n-3条对角线造成。而每一条为拆分时都计数了一次,即重复度为n-3。所以有(n-3)hn= n(h3hn-1+h4hn-2+…+hn-2h4+hn-1h3)/2。由于h2=1,所以(n-3)hn=n(hn+1-2 hn)/2,整理得hn+1=(4n-6) hn/n将此公式与公式2进行比较可知此公式相当于Cn-1= Cn-2。所以hn+1= Cn-1, 因而只需根据公式2计算出Cn,即可得出此问题的解。Cn计算函数如下。

Long Catalan(int n){

long c;

if(n==0||n==1) c=1;

else c=(4*n-2)*Catalan(n-1)/(n+1);//Catalan递推公式2

return c;

}

此算法的时间复杂度为O(n)。

（二）二叉树计数问题

求有n个结点互不相似的二叉树的数目bn及有序树的数目tn。

直观可知b0=1(空树),b1=1(根结点)，当n≥2时,n个结点二叉树除根结点外,其余的n-1个结点可分为有k个结点在左子树上且n-k-1个结点右子数上。如图3所示。

所以bn = (n≥1),b0=1。即满足公式1,所以有n个结点不相似的二叉树的目bn恰好为第n个Catalan数即bn= Cn=(n=0,1,2,…)，由树和二叉树的转换可知,一棵树可转唯一地换成一棵没有右子树的二叉树,反之亦然。所以有n个结点的不同形态的树的数目tn和具有n-1个结点互不相似的二叉树的数目bn-1相同，即tn= bn-1= 。

（三）出栈计数问题

1,2,…,n按顺序进栈,其出栈方式有多少种?

此问题相当于一棵有n个结点的二叉树,对其结点从1到n编号并且在做中序遍历时其结点进栈顺序为1,2,…,n,求所有的出栈方式。因一棵二叉树中序遍历时唯一对应一种进栈(1,2,…,n顺序)和出栈顺序,反之,一种进栈顺序为1,2,…,n再加上一种出栈顺序唯一的对应一棵二叉树。所以出栈方式共有Cn= 种。

（四）矩阵连乘积问题

给定n个矩阵{A1,A2,…,An},考察这n个矩阵的连乘积A1A2…A。的完全加括号方式有多少种?并求哪一种完全加括号方式其乘积计算量最小?

完全加括号的矩阵连乘积可递归定义为：

1.单个矩阵是完全加括号的。

2.矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号,即A=(BC)。

对于n个矩阵的连乘积,设其不同的计算次序为P(n)。由于可以在第k个和第k+1个矩阵之间将原矩阵序列分为2个矩阵子序列,k=1,2,…,n-1,然后分别对这2个矩阵子序列完全加括号,最后对所得的结果加括号,得原矩阵序列的一种完全加括号方式。由此可以得到关于P(n)的递推公式如下：

P(n)=(k>1) 且 P(1) = 1。即满足公式1,所以n个矩阵的连乘积A1A2…An的完全加括号方式有P(n)= Cn-1= 种方式。求计算量最小的加括号方式可采用穷举法，即循环 次,在每次循环中记录本次循环所对应的矩阵连乘积所需数乘次数,挑出最小值即可。但这样做的计算量太大,由Stirling公式n!~ 可得Cn= =Ω(4n/n3/2)。也就是说P(n)随输入规模n的增加呈指数增长。因此, 穷举法不是一个有效的算法。实际上计算量最小的加括号方式可采用动态规划来解决,这里从略。

三、结束语

如果一个问题的数学模型与Catalan数的递推公式相符合，其算法设计与分析可利用Catalan数来解决。使看似复杂的问题变的容易，可以获得较高的时间和空间效率。

参考文献：

[1]Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein. INTRODUCTION TO ALGORITHMS(Second Edition)[M].The MIT Press,2001

[2]Richard A.Brualdi.Introductory Combinatorics(Third Edition)[M].Prentice Hall,2001

[3]卢开澄.组合数学(第2版)[M].清华大学出版社,2001

[4]吴文虎,孙贺.程序设计中的组合数学[M].清华大学出版社,2005

[5]王晓东.算法设计与分析[M].清华大学出版社,2003

基金项目：国家自然科学基金项目可信移动互联网(60633020)

推荐访问:算法 分析 Catalan