我又双叒叕碰到卡特兰数啦！
本篇文章说一说我遇到的卡特兰数。
起因
在数据结构的作业中遇到了一道「求出栈序列的个数」的题目，穷举的话会很可怕，想了好久也没弄出来。在网上一查，嗯，确实是递推的问题，只是递推公式比较复杂。我仔细一瞧，嘿！这结果居然是卡特兰数！正巧最近没啥想法，不如趁机整理一下这方面的题目吧 ！
卡特兰数的介绍
首先放一张卡特兰数规律的表格。
| | | | | | 42 |
| ---- | ---- | ---- | ---- | ---- | ---- |
| | | | | 14 | 42 |
| | | | 5 | 14 | 28 |
| | | 2 | 5 | 9 | 14 |
| | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 1 | 1 | 1 | 1 |在对角线上的就是卡特兰数，1、1、2、5、14、42……（第零项第一项都是 1）
这个玩意儿是组合数学中的一个经典的数列，很重要，我一个学 CS 的都已经第二次遇到它了，而且每次都没做出来
递推公式
$$ C_{n+1}=C_0C_n+C_1C_{n-1}+…+C_nC_0 $$
这个是最基本的递推关系，但有些复杂，下面是简化后的版本，但不太容易理解：
$$ C_n=C_n(4*n-2)/(n+1) $$
解出来的结果是：
$$ C_n=C(2n,n)/(n+1) $$
卡特兰数的应用
出栈序列的种类
一道数据结构的作业题，好难……
栈结构，后进先出，1 到 n 共 n 个数进出栈，问有多少种出栈的顺序？
当时题目设置 n 为 6，结果是 132，穷举的话很难准确完成。
所以这里面一定有什么规律，或者说一定是有递推关系的。
我们要思考的是如何把「大问题」分解成一个个「小问题」。
- n=1，1 种。
- n=2，2 种；
- n=3，5 种。
从 n=4 开始，我们可以分析递推关系了。
两个方向：
- 按照 1 的出栈位次分类
- 按照第一个出栈的数分类
我毫不犹豫的选了第二种，然后什么关系也没弄出来。
下面对于 n=4 按照第一种方法分类：
如果 1 第一个出来，那么剩余 3 个数，f(3)。
如果 1 最后一个出来，那么前三个已经出来了，f(3)。
如果 1 第二个出来，那么前面那个先出来，f(1)，后面还有两个，f(2)，所以是 f(1)*f(2)。（这里我们可能会忽略 f(1) 这一个因子，不过如果再分析一下 n=5 的情况就明白这里应该是 f(1)了。）
如果 1 第三个出来，那么前面 f(2)，后面 f(1)。
再对 n=5 一分析就能发现规律了！
得到的就是卡特兰数的基本递推公式。
凸多边形分割成三角形
将一个 n 条边的凸多边形区域分成三角形区域的方法数？
n 条边，砍一刀，变成一个 i+1 条边，一个 n-i+1 条边。
$$ f(n)=f(3)*f(n-1)+f(4)*f(n-2)+f(5)*f(n-3)+…+f(n-1)*f(3) $$
节点组成二叉树
给定 n 个节点，能构成多少种不同的二叉树？
对角线行走路线
想象一张正方形格子地图，从左下角走到右上角，不「穿过」这条对角线的行走方式有多少种？
这个是我刚才突然看到的熟悉的问题。
这应该是我第一次遇到卡特兰数的地方，在我高三做的排列组合题目时遇到的问题，当时在答案解析上看到「卡特兰数」这个名字，就觉得很厉害。
引申：汉克尔矩阵
n=4 的汉克尔矩阵
| 1 | 1 | 2 | 5 |
| ---- | ---- | ---- | ---- |
| 1 | 2 | 5 | 14 |
| 2 | 5 | 14 | 42 |
| 5 | 14 | 42 | 132 |无论 n 取多少，这个矩阵的行列式的值都为 1。
进一步，移动一下。
n=4
| 1 | 2 | 5 | 14 |
| ---- | ---- | ---- | ---- |
| 2 | 5 | 14 | 42 |
| 5 | 14 | 42 | 132 |
| 14 | 42 | 132 | 429 |它的行列式的值也是 1。
很神奇吧！
卡特兰数的本质探究
Catalan 数出现在很多看似完全不同的计数问题中，证明方法亦有多种不同的角度。比如买票找零问题、格路径问题等多以通项公式证明，二叉树问题、凸多边形三角划分问题等多以递推公式证明等。————《卡特兰数的一种同构证明》
网上有大量的文章整理收集卡特兰数的应用，我就只提了四种，不充当分母了。
这里有一篇论文，卡特兰数的一种同构证明，我摘录其中的重要定理作为笔记。
- 定理
n 个 +1 和 n 个 -1 组成的 2n 项的序列
$$ a_1、a_2、a_3…a_{2n} $$
若其部分和满足
$$ a_1+a_2+a_3…+a_k>=0 $$
则称之为可接受序列，则次序列的个数等于第 n 个卡特兰数。
（一针见血的指出了一部分问题的本质！）
格路径问题的证明：
非负整数 n，从 (0,0) 到 (n,n) 的下对角线矩形格路径的条数等于第 n 个卡特兰数。
把向上设为 +1，向右设为 -1，于是问题巧妙转化为可接受序列的问题了。
借书还书问题：
图书馆排队，n 人还同一本书，n 人都要借同样的同一本书，整个过程图书馆没有缺书，问排队方式的种类？
还书 +1，借书 -1，于是问题又巧妙地……
进栈出栈问题：
进栈 +1，出栈 -1，出栈顺序等价于可接受序列的种类。
卖东西找零问题：
阿里有道题目，一个商品 5 元，8 个人分别拿 5 元来买，又有 8 个人分别拿 10 元买 1 个，如果不出现无法找零的情况，有多少种排队方式？
别看 5 和 10 不相等，其实本质还是一样的。
5 元就是 +1，10 元就要找零，就是 -1。
所以这里也是同样的思路。
最后
看似毫不相关的几个问题，居然都指向了卡特兰数，数学是如此奇妙！
但深入讨论后不难发现，卡特兰数问题的本质便是「可接受序列的种类」的问题。
不要强行记忆那么多应用，而要找到本质，共同点，然后才能解决新问题。
最后，感谢这篇论文的作者，让我更加深入的理解卡特兰数。