卡特兰(Catalan)数入门详解

[也许更好的阅读体验CSDN](https://blog.csdn.net/Morning_Glory_JR/article/details/102760802) [也许更好的阅读体验博客园](https://www.cnblogs.com/Morning-Glory/p/11747744.html) # 基本概念 ## 介绍 学卡特兰数我觉得可能比组合数要难一点，因为组合数可以很明确的告诉你那个公式是在干什么，而卡特兰数却像是在用大量例子来解释什么时卡特兰数 这里，我对卡特兰数做一点自己的理解 卡特兰数是一个在组合数学里经常出现的一个数列，它并没有一个具体的意义，却是一个十分常见的数学规律 对卡特兰数的初步理解：有一些操作，这些操作有着一定的限制，如一种操作数不能超过另外一种操作数，或者两种操作不能有交集等，这些操作的合法操作顺序的数量 为了区分组合数，这里用$f_n$表示卡特兰数的第$n$项 从零开始，卡特兰数的前几项为$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790\ldots$ ## 定义 **递归定义** $f_n=f_0*f_{n-1}+f_1*f{n-2}+\ldots+f_{n-1}f_{0}$，其中$n\geq 2$ **递推关系** $f_n=\frac{4n-2}{n+1}f_{n-1}$ **通项公式** $f_n=\frac{1}{n+1}C_{2n}^{n}$ 经化简后可得 $f_n=C_{2n}^{n}-C_{2n}^{n-1}$ 只要我们在解决问题时得到了上面的一个关系，那么你就已经解决了这个问题，因为他们都是卡特兰数列 --- # 实际问题 先用一个最经典的问题来帮助理解卡特兰数 去掉了所有的掩饰，将问题直接写出来就是 ## 例题1 在一个$w\times h$的网格上，你最开始在$\left(0,0\right)$上，你每个单位时间可以向上走一格，或者向右走一格，在任意一个时刻，你往右走的次数都不能少于往上走的次数，问走到$\left(n,m\right),0\leq n$有多少种不同的合法路径。 **合法路径个数为$C_{2n}^{n}-C_{2n}^{n-1}$** 直接求不好，考虑求有多少种不合法路径 路径总数为在$2n$次移动中选$n$次向上移动，即$C_{2n}^{n}$ 画一下图，我们把$y=x+1$这条线画出来，发现所有的合法路径都是不能碰到这条线的，碰到即说明是一条不合法路径 先随便画一条碰到这条线的不合法路径，所有的不合法路径都会与这条线有至少一个交点，我们把第一个交点设为$\left(a,a+1\right)$ 如图  我们把$\left(a,a+1\right)$之后的路径全部按照$y=x+1$这条线对称过去 这样，最后的终点就会变成$\left(n-1,n+1\right)$  由于所有的不合法路径一定会与$y=x+1$有这么一个交点 我们可以得出，所有不合法路径对称后都唯一对应着一条到$\left(n-1,n+1\right)$的路径 且所有到$\left(n-1,n+1\right)$的一条路径都唯一对应着一条不合法路径（只需将其对称回去即可） 所以不合法路径总数是$C_{2n}^{n-1}$ 那么合法的路径总数为$C_{2n}^{n}-C_{2n}^{n-1}$ 这是一个非常好用且重要的一个方法，其它的问题也可以用该方法解决 即**找到不合法路径唯一对应的到另一个点的路径** 如[网格计数](https://blog.csdn.net/Morning_Glory_JR/article/details/102689403) --- ## 方法 先将方法写在前面吧 相信大家都听过烧开水这个数学小故事吧 和学习数学一样，**转化**是基本思路，将一个问题转化为另外一个已经解决了的问题是最重要的 --- ## 01序列 你现在有$n$个$0$和$n$个$1$，问有多少个长度为$2n$的序列，使得序列的任意一个前缀中$1$的个数都大于等于$0$的个数 例如$n=2$时 有$1100,1010$两种合法序列 而$1001,0101,0110,0011$都是不合法的序列 **合法的序列个数为$C_{2n}^{n}-C_{2n}^{n-1}$** 我们把出现一个$1$看做向右走一格，出现一个$1$看做向上走一格，那么这个问题就和上面的例题$1$一模一样了 **拓展** 如果是$n$个$1,m$个$0$呢？ 不过是最后的终点变为了$\left(n,m\right)$罢了 如果是$1$的个数不能够比$m$少$k$呢 我们只需将$y=x+1$这条线上下移动即可 --- ## 括号匹配 你有$n$个左括号，$n$个右括号，问有多少个长度为$2n$的括号序列使得所有的括号都是合法的 **合法的序列个数为$C_{2n}^{n}-C_{2n}^{n-1}$** 要使所有的括号合法，实际上就是在每一个前缀中左括号的数量都不少于右括号的数量 将左括号看做$1$，右括号看做$0$，这题又和上面那题一模一样了 --- ## 进出栈问题 有一个栈，我们有$2n$次操作，$n$次进栈，$n$次出栈，问有多少中合法的进出栈序列 **合法的序列个数为$C_{2n}^{n}-C_{2n}^{n-1}$** 要使序列合法，在任何一个前缀中进栈次数都不能少于出栈次数$\ldots$ 后面就不用我说了吧，和上面的问题又是一模一样的了 --- ## 312排列 一个长度为$n$的排列$a$，只要满足$i<j<k$且$a_j<a_k<a_i$就称这个排列为$312$排列 求$n$的全排列中不是$312$排列的排列个数 答案也是卡特兰数 我们考虑$312$排列有什么样的特征 如果考虑一个排列能否被$1,2,3,\ldots,n-1,n$排列用进栈出栈来表示 那么$312$排列就是所有不能被表示出来的排列 那么这个问题就被转化成进出栈问题了 --- ## 不相交弦问题 在一个圆周上分布着 $2n$个点，两两配对，并在这两个点之间连一条弦，要求所得的$2n$条弦彼此不相交的配对方案数 当$n=4$时，一种合法的配对方案为如图  **合法的序列个数为$C_{2n}^{n}-C_{2n}^{n-1}$** 这个问题没有上面的问题那么显然，我们规定一个点为初始点，然后规定一个方向为正方向 如规定最上面那个点为初始点，逆时针方向为正方向 然后我们把一个匹配第一次遇到的点（称为起点）旁边写一个左括号$($，一个匹配第二次遇到的点（称为终点）旁边写一个右括号$)$ 如图  看出来吗，在规定了这样的一个顺序后，在任意一个前缀中起点的个数都不能少于终点的个数 于是这又是一个卡特兰数列了 --- ## 二叉树的构成问题 有$n$个点，问用这$n$个点最终能构成多少二叉树 答案仍然是卡特兰数列 这个问题不是用上面的方法，是用递归定义的卡特兰数 一个二叉树分为根节点，左子树，右子树 其中左子树和右子树也是二叉树，左右子树节点个数加起来等于$n-1$ 设$i$个点能构成$f_i$个二叉树 我们枚举左子树有几个点可得 $f_n=f_0*f_{n-1}+f_{1}*f_{n-2}+\ldots+f_{n-1}*f_{0}$ 这个和卡特兰数列的递归定义是一模一样的 --- ## 凸多边形的三角划分 一个凸的$n$边形，用直线连接他的两个顶点使之分成多个三角形，每条直线不能相交，问一共有多少种划分方案 答案还是卡特兰数列 我们在凸多边形中随便挑两个顶点连一条边，这个凸多边形就会被分成两个小凸多边形，由于每条直线不能相交，接下来我们就只要求这两个小凸多边形的划分方案然后乘起来即可 和二叉树的构成问题一样，我们枚举大凸多边形被分成的两个小凸多边形的大小即可 --- ## 阶梯的矩形划分 一个阶梯可以被若干个矩形拼出来 图示是两种划分方式   像下图是不合法的划分方式  问，一个$n$阶矩形有多少种矩形划分 答案仍然是卡特兰数列 我们考虑阶梯的每个角 如图  每个角一定是属于不同的矩形的，我们考虑和左下角属于一个矩形的是哪个角 这个矩形将这个梯形又分成两个小梯形，如图  于是我们又可以写出递推式了 和卡特兰数列的递归式是一样的 卡特兰数就讲这么多吧