资源描述：
《毕业论文《探究catalan数及应用》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、探究CataIan数及应用摘要：本文探讨了Catalan数的递推关系，并用多种方法（递推法，多项式法及微分方程法）推导了Catalan数的计算公式。通过图解形式形象的给出了Catalan问题与其它几个重要问题的对应关系。列举了多种关于Catalan数最典型的应用，并给出了部分问题的证明或图解。关键词：Newton二项式定理,Euler多边形分割问题，Catalan数，递推关系，排列。1.引言对于f（兀；Q）二（1+兀）"的幕级数展开式我们很容易由Newton二项式定理直接写出：fs）w+g“.+牛加宀2!若当V时，我们有:f(w)=(g)F»+、1r1、(\<1)
2、1--12…—YI丿22〔2丿U丿<2丿12(Z7+1)!1+丄兀+二宀・・・+223(-1)"l*l*3*・・・*(2n—1)卄］S+l)「0兀223(i)"1(2心兀(〃+1)「2"+厂2“*斤！ZH11+丄兀+寺223(-iy22/,+1(-ir22n+,oo二1+为M=O通过上面的式子，我们发现了一个很特别的表达式一c二（巾＞O）。我们可以71+1尝试着写出它的前16个数：1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845。经过研究这16个数,我们发现了一个非常有
3、趣的规律：在第2*（20,1,2,3,4）处的数为奇数。经过前人的研究，不仅仅当20,1,2,3,4时有此结论成立，当k为任何非负整数吋，此结论均成立。让我们再来思考这么一个被人们称为Euler多边形分割问题的问题：用n-1条不相交的对角线将一个凸n+2边形分割为n个三角形的方法数用「表示，那么这「为多少？nfi当一看完这个问题，你或许会不自觉的画出下列分别当“2,3,4,……，时，所满足题意的图形來：n分割图C”（第一页）画到这儿，己没有必要再画下去了，因为我们己经惊奇的发现这与上而那列数中的一段完全吻合。此时此刻，我们己经能很好严叫1的神奇。这个数列就是木文所将
4、要讨（第二页）论的Catalan数。1.关于Catalan数的递推公式及证明定理：Catalan数c满足以下递推关系：(i)=Co*C^C.*Cw_.+…+CH_.*C.+C>t*Co；(ii)-Oc,,=(c.*c,,-.c2*c._2+•••+Cfl-2*C2+*c.)(i)的证明：如图2.1所示的凸n+3边形，以V1V/f+3作为三角形的一条边，三角形的另一个顶点为y,,k=2,3,4,……,n+2,三角形“认讥+3将时3边形分割成一边为k边形,另—边为n-k+4边形。V2（图2.2）根据乘法法则，以V1讥口心为一剖分三角形的剖分数应为C-2*C2根据加法法则
5、有：k二2,3，…,n+2,所得的剖分各不相同。C“+
6、=Co*C“+C*C„-}+…+Cn-*C]+C“*Co(ii)的证明：如图2.2所示的凸n+2边形，从口分别到n-1个顶点｛y3^p4^•)引出n-l条对角线，以V1Va.对角线为例，将凸n+2边形分解为一边为k边形，另一•边为n-k+4边形的情形。因此，以VlVk为剖分线的n边形剖分数目应为k二3,4,…，n+1o对23,4,…,n—l求和r、第三页丿V/M点改为V2^V3^-^V„+2也有类似的结果。山于每一条对角线有两个端点，而且每个剖分总有F1-1条对角线，对每条对角线都计算一次得：进2(c*u
7、,一+c木c,-2+…+c,-.y2+oc)②注意到每个凸n+2边形的剖分都通过n-l条对角线，所以式②将剖分方案数重复计算了n-1次，故有：Sj)C.=宁(c.*C,-,+U*C.-2+…+C.-2*C,+cc)通过观察上述定理中的两个递推关系(特别是两个公式的右边)，我们发现育卞述关系成立：5一1)0”=宁匕“-(CVC“+CVC』，lflJC7o=10S-1）C“=笃^（6-2C,J通过简单处理，我们有:由此,我们可以得出如下推论:推论：Catalan数满足递推关系：q4-C„-i1.Catalan数的计算公式及推导。3.1.递推关系法由推论及Co=l'我们
8、有:Z=4-V4n—2n+1C.-i2（2nl）=2（2—讥2（2—3^2（2—5人,2*3,2*!m+1nn-3252(2程一1几2(2程一3几2(2程一5几土2步3主2*1/?+1nn—1322"（az+1）!*（2刃_1）*（2n_3）*（2m_5）*•••*3*12"主（2小！=（2小！S+1）!2n*n!n!*S+l）!1永⑵dn+1（/?!）23.2.多项式法第四页由于C)=C=1'设G(X)二C°+O+C2x2+Ck+……=EcXJt=o则:GD=CVC；+(CVC+CVC>+(CVC2+CrC+C2*C»2+y=o/=()H4-1/=0山
