什么是Catalan数.pdf

什么是Catalan 数 说到Catalan 数，就不得不提及Catalan 序列，Catalan 序列是一个整数序列，其通项公式是 我们从中取出的 就叫做第 n 个 Catalan 数，前几个 Catalan 数是：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, …咋看之下没什么特别的，但是Catalan 数却是许多计数问题的最终形式。 Catalan 数的一些性质 Catalan 数的基本公式就是上个部分所列出的那样，但是却有一些变形和具体的性质： 1、 这 是 根 据 原 来 的 式 子 推 导 出 来 的 ， 大 概 过 程 是 这 样 的 ： 2、 这个递推式很容易可以从原来的式子中获得 3、 4 、 5、 这个是Catalan 数的增长趋势。 Catalan 数在组合计算中的应用 在《组合数学》（机械工业出版社）一书中，介绍Catalan 数是由其一个应用推导出的公式， 其具体的描述如下： n 个+1 和n 个-1 构成2n 项 ，其部分和满足 的序列个数等于第n 个Catalan 数 。 其证明也不难，我们假设不满足条件的序列个数为 ，那么就有 。剩下的 工作就是求 了，我们假设有一个最小的k 令 。由于这里k 是最小的， 所以必有 ，并且k 是一个奇数。此时我们将前k 项中 的+1 变为-1，将-1 变为+1,那么就得到一个有(n+1)个+1 和(n-1)个-1 的序列了，这样的序列个 数就是我们要 求的 ，数值大小为 。那么我们就得到了 ，就是我们前面的公式。 在具体的组合数问题中，很多都可以转换为Catalan 数进行最后的计算，如下： 1、如上文所说，对于任意的k，前k 个元素中-1 的个数小等于+1 的个数的序列计数，我们 可以不停地变换形式，比如将-1 看成右括号，+1 看成左括号，就变成了合法括号表达式的 个数。比如2 个左括号和2 个右括号组成的合法表达式有 种，是()()和(())。 2、既然如上一点都把括号加上去了，那么顺便就再次转换，n+1 个数连乘，乘法顺序有 种，比如我们三个数连乘a*b*c，那么等于在式子上加括号，有2 种乘法顺序，分别是(ab)c 和a(bc) 。貌似对应关系比较模糊，我们取n 为3 来看看，n 为3 的时候就是4 个数相乘了， 那么我们设为abcd，最初的标号定在a 上，我们对于n 为3 得到合法的括号序列有5 个， 分别是：((()))，()(())，()()()，(())()和(()())，那么我们将一个左括号看成是当前操作数指针往 右移动一个位置，一个右括号看成是当前操作数和左边最近的一块操作数相乘起来，那么对 应的五个表达式就是：a(b(cd))，(ab)(cd)，((ab)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 上的一张图片说明问题： 这里要求满二叉树，实际上就是在上一点的每个子节点的空儿子上都加上叶子，就形成了我 们的图了，那么我们要求的结果就是Catalan 数。 5、对于一个n*n 的正方形网格，每次我们能向右或者向上移动一格，那么从左下角到右上 角的所有在副对角线右下方的路径总数为 。同样引用Wikipedia 上的一张图片来表示： 我们将一条水平边记为