什么是Catalan数

《什么是Catalan数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、什么是Catalan数说到Catalan数，就不得不提及Catalan序列，Catalan序列是一个整数序列，其通项公式是我们从中取出的就叫做第n个Catalan数，前几个Catalan数是：1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,…咋看之下没什么特别的，但是Catalan数却是许多计数问题的最终形式。Catalan数的一些性质Catalan数的基本公式就是上个部分所列出的那样，但是却有一些变形和具体的性质：1

2、、这是根据原来的式子推导出来的，大概过程是这样的：2、这个递推式很容易可以从原来的式子中获得3、4、5、这个是Catalan数的增长趋势。Catalan数在组合计算中的应用在《组合数学》（机械工业出版社）一书中，介绍Catalan数是由其一个应用推导出的公式，其具体的描述如下：n个+1和n个-1构成2n项，其部分和满足的序列个数等于第n个Catalan数。其证明也不难，我们假设不满足条件的序列个数为，那么就有。剩下的工作就是求了，我们假设有一个最小的k令。由于这里k是最小的，所以必有，并且k是一个奇数。此时我们将前k项中的+1变为-1

3、，将-1变为+1,那么就得到一个有(n+1)个+1和(n-1)个-1的序列了，这样的序列个数就是我们要求的，数值大小为。那么我们就得到了，就是我们前面的公式。在具体的组合数问题中，很多都可以转换为Catalan数进行最后的计算，如下：1、如上文所说，对于任意的k，前k个元素中-1的个数小等于+1的个数的序列计数，我们可以不停地变换形式，比如将-1看成右括号，+1看成左括号，就变成了合法括号表达式的个数。比如2个左括号和2个右括号组成的合法表达式有种，是()()和(())。2、既然如上一点都把括号加上去了，那么顺便就再次转换，n+1个数

4、连乘，乘法顺序有种，比如我们三个数连乘a*b*c，那么等于在式子上加括号，有2种乘法顺序，分别是(ab)c和a(bc)。貌似对应关系比较模糊，我们取n为3来看看，n为3的时候就是4个数相乘了，那么我们设为abcd，最初的标号定在a上，我们对于n为3得到合法的括号序列有5个，分别是：((()))，()(())，()()()，(())()和(()())，那么我们将一个左括号看成是当前操作数指针往右移动一个位置，一个右括号看成是当前操作数和左边最近的一块操作数相乘起来，那么对应的五个表达式就是：a(b(cd))，(ab)(cd)，((ab)

5、c)d，(a(bc))d和a((bc)d)，他们之间是一一对应关系。3、n个节点的二叉树的所有可能形态数为，这一点很容易证明，我们考虑随便取一个节点作为根，那么他左边和右边的儿子节点个数就确定了，假定根节点标号为x，那么左子树的标号就从1到x-1,共x-1个，右子树的标号就从x+1到n，共n-x个，那么我们的x从1取到n，就获得了所有的情况数。这个式子就是我们性质3的式子。4、n个非叶节点的满二叉树的形态数（对称后得到的二叉树除非自己本身对称，否则算是不同），这里取Wikipedia上的一张图片说明问题：这里要求满二叉树，实际上就是在

6、上一点的每个子节点的空儿子上都加上叶子，就形成了我们的图了，那么我们要求的结果就是Catalan数。5、对于一个n*n的正方形网格，每次我们能向右或者向上移动一格，那么从左下角到右上角的所有在副对角线右下方的路径总数为。同样引用Wikipedia上的一张图片来表示：我们将一条水平边记为+1,垂直边记为-1,那么就组成了一个n个+1和n个-1的序列，我们所要保证的就是前k步中水平边的个数不小于垂直边的个数，换句话说前k个元素的和非负，就是我们关于Catalan数的定义。6、凸n+2边形进行三角形分割（只连接顶点对形成n个三角形）数：7、

7、n个数入栈后的出栈的排列总数是。例如1,2,3入栈的出栈排序有123，132，213，231和321五种8、对于集合的不交叉划分的数目为，这里解释一下不交叉划分，我们对于集合{a,b}和{c,d}，假设他们组成了两个区间[a,b]和[c,d]，我们假设两个区间不重合，那么以下四种情况当做是不交叉的：a

8、划分为一个不交叉划分。此时不交叉的划分数就是我们的了，证明也很容易，我们将每个子集中较小的数用左括号代替，较大的用右括号代替，那么带入原来的1至2n的序列中就形成了合法括号问题，就是我们第二点的结论。例如我们的集合{1,