fullfocus--年轻不怕失败

2007-07-21

关键字: 数据结构算法卡特兰数分治策略

先来看看CATALAN数是怎么定义的。（http://www.ekany.com/wdg98/zhsx/2/2_11.htm）

2.11 Catalan 数

这一节讨论Catalan数,其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.本节将举出一些,后面还将见到.

一个凸n边形,通过不相交于n边形的对角线,把n边形拆分成若干三角形,不同拆分的数目用h_n表示.例如五边形有如下五种拆分方案，故h_n=5

图 2-11-1

1.递推关系

定理：

证明：

（a）的证明：如图2－11－1所示，以v₁v_n+1作为一个边的三角形，将凸n+1边形分割成两部分，一部分是 k边形，另一部分是n-k+2边形，k=2,3,^...,n即v_k点可以是v₂,v₃,^...,v_n点中任意一点。依据加法法则有

图 2－11－3

(b) 的证明：如图2－11－3所示，从v₁点向其它n-3个顶点(v₃,v₄,^...,v_n-1)可引出n-3条对角线。对角线v₁v_k把n边形分割成两个部分，因此以v₁v_k对角线作为拆分线的方案数为h_kh_n-k+2。

v_k可以是v₃,v₄,^...,v_n-1中任一点，对所有这些点求和得h₃h_n-1+h₄h_n-2+^...+h_n-2h₄+h_n-1h₃

以v₂,v₃,^...,v_n取代点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，作

（2－11－3）式并不就给出剖分数，无疑其中是有重复的。其重复度是由于一个凸n边形的剖分有n-3条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了n-3次即（2－11－3）式给出的结果是h_n的n-3倍。

（2－11－1）式和（2－11－2）式都是非线性的递推关系。

2.Catalan 数计算公式

由（2－11－1）式及h₂=1故得

由

整理得

令