catalan数及其运用.doc

数及其运用作者： 学号： 指导老师：【摘要】：本文对数的历史由来的简单介绍、通过历史问题引出其定义得出其表达式并求解出数的通式，给出数的一些性质，好以上这些工作之后通过一些实例展现出数的一些实际应用。由历史由来我们可以提高读者对数学历史的深究，增加对数学历史的了解提高对数学学习的兴趣以及对研究数热情；由历史上Euler研究凸多边形的实例给出数的定义让读者对数有一个一定深度的了解；通过解析其一般表达式得出数的通项对数进行深度的剖析；并由数的通项我们可以计算出数数列中的一些项；从数的一些性质中我们可以了解数变形更加符合默写实际情况突出数的灵活性；最终的研究都是为了在学习和生活中的实际应用所以在应用中我们不仅给出了在学术上的一些应用还给出了数在社会生活中的一些呈现。【关键词】：数 组合数学 路径 二叉树【引言】：数Cn是组合数学中应用广泛的重要计数函数，它是比利时数学家 (18141894)在1838年研究组合数学问题时发现并提出来的。事实上，大数学家在17581759年研究凸多边形的三角形剖分问题时，就已经发现了该计数函数。数有明显的组合意义，在唱售票问题、路径问题和一些实际问题中有着广泛的应用。数的定义：我们由提出的对凸多边形的不同的三角形剖分的个数来研究其定义。问题：在一个凸变形中，通过插入内部不相交的对角线将其分成一些三角形区域，问有多少种不同的分法？解：我们令表示分一个条边的凸多边形为三角形的方法数，并规定.当时，三角形不需要对角线，所以.当时，插入对角线的方法有两种，所以,如下图（a,b）所示。 (c)当时，对一个凸边形，它的顶点我们分别用来表示，如图（c）,取定多边形的一条边,任取多边形的顶点（）,将分别与之间连线，得三角形，三角形将凸多边形分成和三部分，其中，为变形，为变形.因此，可以用中方法划分，可以用中方法划分，所以 （1）此时我们得出数的定义如下：令，满足递归式， 的数就是数.数的通项求解：那这个式子的解法很多，我们这里的解法如下：问题：求解 解：由于这个递推关系不是线性的，并不依赖于前面的某个固定值，而是依赖与前面的所有值。我们令生成函数：将与自己相乘：将=和的递推关系代入得到： 解得；由的定义知道，验证上述根只有成立，所以生成函数：;根牛顿二项式定理，将中的项展开：;= 所以：=所以我们得出其通项为：这就是我们要研究的数数数列：我们得到数的的通项，由此我们代入数据就可以得到一连串数列，我们称之为数数列列数是：1，1，2，5，14，42， 132，429，1430，4862，16796，58786，208012， 742900，2674440， 9694845，35357670， 咋看之下没什么特别的，但是数却是许多计数问题的最终形式。数的性质：1、 （简单推导：2、3、 4、5、 这个是数的增长趋势。数的经典运用：1括号化问题：矩阵链乘：，依据乘法结合律，不变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？解：设对个数的乘机有种方案，则我们可以得出如下方程组：容易看出它和数满足同一个递推关系。出入栈问题：一位大城市的律师在他住所以北个街区和以东个街区处工作。每天她走个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？图（4）解：如图（4）所示，先考虑对角线下方的路径。这些路径都是从）点出发，经过点及点到达点的我们可以把他看作是从点出发到达点的不接触对角线的路径。从点到点的所有路径数为.对其中任意一条接触对角线的路径，我们可以把他从最后离开对角线的点如图（4中的A点）到点之间的部分关于对角线做一个反射，就得到一条从点出发经过点到达点的路径。反之，任何一条从点出发，穿过对角线而到达点的非将路径，也可以通过这样的反射对应到一条从点出发接触到对角线而达到点的路径。从达到的路径数为有对称性可知，所求路径数为3,二叉树问题个节点的二叉树的所有可能形态数为.证明，我们考虑随便取一个节点作为根，那么他左边和右边的儿子节点个数就确定了.根节点标号为，那么左子树的标号就从到,共个，右子树的标号就从到，共个，那么我们的从取到，就获得了所有的情况数.这个就是我们性质3的式子.4、Catalan数问题的变形个人排队买票，并且满足，票价为50元，其中个人各手持一张50元钞票，个人各手持一张100元钞票，除此之外大家身上没有任何其他的钱币，并且初始时候售票窗口没有钱，问有多少种排队的情况数能够让大家都买到票。解：这个题目是数的变形，不考虑人与人的差异，如果m=n的话那么就是我们初始的数问题，也就是将手持50元的人看成是+1，手持100元的人看成是-1，任前k个数值的和都非负的序列数。这个题目区别就在于的情况，此时我们仍然可以用原先的证明方法考虑，假设我们要的情况数是，无法让每个人都买到的情况数是，那么就有，此时我们求，我们假设最早买不到票的人编号是，他手持的是100元并且售票处没有钱，那么