Catalan数

问题引入

使用个相同的节点可构造多少种不同的二叉树？其中。

设表示用个节点构造的的二叉树形态的个数，不难发现 ,为空树。

由于非空的二叉树是由根节点、左子树、右子树组成的，考虑对左子树节点数量进行枚举，所以有：

这里序列就是序列。

基本模型

模型 1：

给定个相同的节点，求可以组成的二叉树形态总数。

一开始就已经说过了，证明略。

模型 2：

长度为的合法括号序列的形态个数。

证明：

记长度为的合法括号序列形态个数为。

首先当为或时，都只有一种形态，即。

考虑的情况，由于这是一个合法的括号序列，所以最后一个括号必定为右括号。

我们再将最后一个右括号所对应的左括号表示出来，括号序列就可以表示为如下形式：A(B)。

其中 A 与 B 必为合法的括号序列（可能为空），枚举 A 的长度，所以有：所以这是卡特兰数。

模型 3：

长度为的序列的出栈序列种数：

证明：

不难发现，对于两种不同的进出栈操作，他们的出栈序列肯定是不同的，所以出栈序列种数其实就是求合法操作数。

那什么样的操作是合法的呢？

我们将一次进栈操作看为一个左括号，一次出栈操作看为一个右括号。

那么，当进栈次数与出栈次数相同，且任何时候当前进栈次数大于等于出栈次数时，

这个出栈序列是合法的，且括号序列也是合法的。

反之也成立。

所以其实这和模型2是一样的。

模型 4：

给定与各个，让他们组成一个长度为的序列，问这样的的个数：对于每一个都有。

证明：

只需要让任何时候的数量大于等于的数量即可。

将看作左括号，看作右括号，其实就是求合法的括号序列数，与模型2一模一样。

模型 5：

给定与各个，让他们组成一个长度为的序列，问这样的的个数：存在一个使得。

证明：

是对于任何，都有的序列个数（大于等于和小于等于是一样的）。

很容易发现这就是不合法的序列的个数。

所以答案为。

模型 6：

一个圆上有个点，求连条线段使得任两线段之间没有交点的方案数（端点处相交也算有交点）。

证明：

将这个点按顺序进行标号（顺时针或逆时针都行），枚举号点与几号点连线，之后这个圆就被分为了两个圆弧。

设答案为，则 $且$ 。

解释：为与连线的节点，要求是为了分成的两端圆弧所含的点的个数都为偶数，和是分成的两段圆弧的点的个数。

设，并使用替换上式中的，有：

序列即为序列

问题扩展

使用个相同的节点可构造多少种不同的二叉树？其中。

显然，如果利用上述公式进行计算，时间复杂度为，无法接受。

定理一：

证明：

使用模型，考虑求出合法方案数。

首先我们知道与各有个，我们先将这个插入个空中，总方案数（可能不合法）即为。

如果一个序列是不合法的，那么说明至少存在一个，使得。

那么我们设这样的中最小的一个为。

假如对于下面这个序列，满足条件的为，那么。

显然会有

举个梨子，假如序列长这个样子：

我们把他的图画出来。

显然，在这个例子中，是第一个使得前缀和的位置。

然后我们将前个数翻转（将变成，将变成）。

显然，会得到的一个有个和个的序列。

上面的序列翻转后得到的序列是。

假设翻转后的序列为。

显然会有。

显然，对于每一个序列，都有一个唯一的序列与之对应。对于每一个序列我们能且只能找出唯一一个序列，这对应了唯一的一的序列。

对于每一个序列，肯定都有一个唯一的序列与之对应。

证明方法差不多，找出第一个使前缀和的位置，并将前个数字翻转。

值得注意的是，因为序列最后一个位置在，所以肯定存在一个合法的。

翻转之后就能变成一个序列。

综上所述，序列与序列是两两对应的，所以他们的数量是相等的。

又因为序列是由个与个组成的，

所以他们的数量都为。

合法序列数量即为。

定理二：

证明：

考虑使用定理一进行推导：

他的另一种形式是：

定理三：

证明：

考虑使用定理二：

注：上述证明参考自：

Catalan通项公式的推导

n对括号的匹配方式以及Catalan数通项公式的推导

【知识总结】卡特兰数 (Catalan Number) 公式的推导

例题

例1

洛谷P1044栈

与模型三一样，证明略。

例2

洛谷P2532树屋阶梯

我们不妨将每一行最后一个格子成为特殊格。

不难发现，每摆放一份钢材，最多只有一个特殊格被覆盖，所以每一次摆放钢材时必须要覆盖到一个特殊格。

显然，最左下角的格子也会被覆盖一次（没错，这是一句废话），那么我们就可以枚举一下和左下角格子一起被覆盖的是哪一个特殊格。

给出时第一次放钢材的方案，供大家理解：

摆放钢材后这个楼梯形状的物品便被分为了两个楼梯，故这是一个 Catalan 数列。

注意：本题没有模，所以需要使用高精。

例3

洛谷P1641生成字符串

与模型一样，证明略。

例4

洛谷P3200有趣的数列

首先我们对题意进行转化，不妨将整个序列拆成两个，一个由原下标为奇数的组成，另一个由原下标为偶数的组成。

显然，这两个序列都是递增的。

那么，题意就可以转化为：对于至中的每个正整数，要么将其放到奇数序列的当前最后一个的后面，要么将其放到偶数序列当前最后一个的后面。

现在我们还有一个条件：就是奇数序列对应数字比偶数序列对应数字小。

这该怎么办呢？其实我们再将这个条件进行转化：

在任意时候，偶数序列数字个数都比奇数序列数字个数多。

所以，当序列长度为时，答案即为。

本题还有一个难点，就是没有保证模数是质数。实际上，我们只要求出中，每个正整数的质因数及个数，再利用公式：

即可计算答案。

目前还没有找到别的啥题要讲，就先咕咕咕。