随笔-28  评论-51  文章-10  trackbacks-0

网站:JavaEye 作者:fullfocus 发表时间: 2007-07-21 07:51 此文章来自于 http://www.JavaEye.com
声明:本文系JavaEye网站原创文章,未经JavaEye网站或者作者本人书面许可,任何其他网站严禁擅自发表本文,否则必将追究法律责任!
原文链接: http://fullfocus.javaeye.com/blog/103543

  先来看看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故得 


       


由 


       


整理得 


       


       


令 


       


  




《 Catalan 数--pku ACM 2084【待解决】 》 的评论也很精彩,欢迎您也添加评论。查看详细 >>





JavaEye推荐
上海乐福狗信息技术有限公司:诚聘技术经理和开发工程师
免费下载IBM社区版软件--它基于开放的标准,支持广泛的开发类型,让您的开发高效自主!
京沪穗蓉四地免费注册,SOA技术高手汇聚交锋.
上海:优秀公司德比:高薪诚聘 资深Java工程师
广州:优易公司:诚聘Java工程师,开发经理
上海:尤恩斯国际集团:诚聘开发工程师
北京:优秀公司NHNChina招聘:WEB开发,系统管理,JAVA开发, DBA



文章来源: http://fullfocus.javaeye.com/blog/103543
posted on 2007-07-21 07:51 fullfocus 阅读(453) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: