先来看看CATALAN数是怎么定义的。(http://www.ekany.com/wdg98/zhsx/2/2_11.htm)
2.11 Catalan 数
这一节讨论Catalan数,其递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.本节将举出一些,后面还将见到.
一个凸n边形,通过不相交于n边形的对角线,把n边形拆分成若干三角形,不同拆分的数目用hn表示.例如五边形有如下五种拆分方案,故hn=5
图 2-11-1
1.递推关系
定理:
证明:
(a)的证明: 如图2-11-1所示, 以v1vn+1作为一个边 的三角形 , 将凸n+1边形分割 成两部分,一部分是 k边形, 另一部分是n-k+2边形,k=2,3,...,n即vk点可以是v2,v3,...,vn点中任意一点。依据加法法则有
图 2-11-3
(b) 的证明: 如图2-11-3所示, 从v1点向其它n-3个顶点(v3,v4,...,vn-1)可引出n-3条对角线。对角线v1vk把n边形 分割成两个部分,因此 以v1vk对角线作为拆分线的方案数为hkhn-k+2。
vk可以是v3,v4,...,vn-1中任一点,对所有这些点求和得h3hn-1+h4hn-2+...+hn-2h4+hn-1h3
以v2,v3,...,vn取代 点也有类似的结果。但考虑到对角线有两个顶点,同一对角线在两个顶点分别计算了一次,作
(2-11-3)式并不就给出剖分数,无疑其中是有重复的。其重复度是由于一个凸n边形的剖分有n-3条对角线,而对其每一条边计数时该剖分都计数了一次,故重复了n-3次即(2-11-3)式给出的结果是hn的n-3倍。
(2-11-1)式和(2-11-2)式都是非线性的递推关系。
2.Catalan 数计算公式
由(2-11-1)式及h2=1故得
由
整理得
令
|