Catalan number
卡特兰数(Catalan Number)
引言
卡特兰数(Catalan number)是组合数学中一个常出现于各种计数问题中的数列,他以中国蒙古族数学家明安图和比利时数学家欧仁·查理·卡特兰的名字命名
基本性质
- 前几项：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786…
- 递推公式：
$$C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdots + C_{n-1} C_0$$ - 通项公式：
$$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$
数学推理
我们以最经典的栈问题举例
问题描述：n个元素的进栈序列为1,2,3,4…..n，则有多少种出栈序列
思路1
将进栈表示为+1，出栈表示为-1，每次要出栈栈内元素要不为空，即每个-1前面必然有一个+1与之对应，出栈序列的前缀和必然大于等于0，且+1的数量等于-1的数量
假设有一个非法出栈序列x，必然有某前几项和小于0，找到第一个前缀和小于0的前缀，它的前缀和也就是-1，如果将其元素进行取反，其前缀和也就变成了1，取反后，-1比1少一个，则+1变为n+1个，-1变为n-1个
进栈出栈总数量为2n，n个进栈，n个出栈，出栈的可能序列总数量为$C_{2n}^{n}$
每一个非法出栈序列，都对应一个对其第一个前缀和为-1的所有元素进行取反的序列，该序列有n+1个进栈，n-1个出栈，非法出栈的可能序列总数量为$C_{2n}^{n+1}$
因此，合法的出栈序列总数为$C_{2n}^{n}$-$C_{2n}^{n+1}$
=$\frac{C_{2n}^{n}}{n+1}$至此，我们得到了卡特兰数的通项为$\frac{C_{2n}^{n}}{n+1}$
思路2
首先，我们设 f(n)=元素个数为n的出栈序列种数。
同时假定，从开始到栈第一次出到空为止，这段过程中第一个出栈的序数是k。特别地，如果栈直到整个过程结束时才空，则k=n。
首次出空之前第一个出栈的序数k将1 ~ n的序列分成两个序列：其中一个是1 ~ k-1，序列个数为k-1；另外一个是k+1 ~ n，序列个数是n-k。
此时，我们若把k视为确定一个序数，那么根据乘法原理，f(n)的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数（一种递归的思想），即选择k这个序数的f(n)=f(k-1)×f(n-k)。
而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f ( n ) = f ( 0 ) f ( n − 1 ) + f ( 1 ) f ( n − 2 ) + … … + f ( n − 1 ) f ( 0 )
这个公式与卡特兰数的递推式一模一样，即为
$$
C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdots + C_{n-1} C_0
$$
最后，其解为第n个卡特兰数，即$\frac{C_{2n}^{n}}{n+1}$
应用
1.括号匹配
问题描述：n对括号，有多少种”括号匹配”的序列
思路：把左括号看成+1，右括号看成-1，每个右括号都有与之唯一对应的左括号，那问题同样可以用进出栈问题一思路来解决，其解等于第n个卡特兰数
其解为$\frac{C_{2n}^{n}}{n+1}$
2.二叉树
问题描述：n+1个叶子结点可以构成多少种形状不同的满二叉树
（n个节点构成的满二叉树）
思路1：
- 深度优先搜索这棵满二叉树，每次向左扩展记为+1，向右扩展记为-1
- 由于每个非叶子结点都有左右两子节点，所以每次必然先向左扩展，再向右扩展，每次右扩展都和左扩展一一对应，同理可以用进出栈思路一来解决
- 叶子数=内部节点数+1，对于n+1个叶子节点，内部节点数为n，每生成一个内部节点，需要向左向右扩展两次，即一共需要扩展2n次
- 可以构成$\frac{C_{2n}^{n}}{n+1}$棵形状不同的满二叉树
- 其解等于第n个卡特兰数
思路2：
可以这么考虑，根占用1个节点，剩下n-1个节点那么剩余的n-1个结点可以有如下的分配方式，T ( 0 , n − 1 ) , T ( 1 , n − 2 ) , . . . , T ( n − 1 , 0 ) 。设T ( i , j ) 表示根的左子树含i个结点，右子树含j个结点。
同理用递归的思想分配左右子树的节点，每个节点都是等价的，其递推公式为：
$$
C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdots + C_{n-1} C_0
$$
其解为$\frac{C_{2n}^{n}}{n+1}$
3.电影购票（找零钱问题）
问题描述：某电影院票价为50元，售票厅处没有零钱，m个人有100元，n个人有50元，问：有多少种排队方式，可以让每个人都买到票（n>m）
思路：
- 将持有50元的人标记为+1，持有100元的人记为-1
- 每个持有100元的人都要和一个持有50元的人匹配
- 同理用进出栈问题思路一解决该问题
- 由于每个人都是独立的个体，总排队方式为$\frac{C_{2n}^{n}}{n+1}$*$m!*n!$
其解为$\frac{C_{2n}^{n}}{n+1}$*$m!*n!$
4.矩阵连乘
问题描述：P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
思路：
- 通过括号化，将p分成两个部分，再分别对这两部分进行括号化（递归思想）
- 括号内的括号化方案只和括号内元素数量有关，与其具体内容无关
- 即总方案可以表示成：
f(n) = f(1)*f(n-1) + f(2)*f(n-2) + f(3)*f(n-3) + f(n-1)*f(1)。f(1)*f(n-1)表示分成(a1)×(a2×a3…×an)两部分 - 计算开始前几项，f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5。结合递归式，不难发现f(n)等于h(n-1)，其解等于第n-1个卡特兰数
其解为$\frac{C_{2n-2}^{n-1}}{n}$
5.凸多边形划分
问题描述：在一个n边形中，通过不相交于n边形内部的对角线，把n边形拆分为若干个三角形，问有多少种拆分方案？
思路：
- 以某条边AB为基准，从其余顶点选择一个顶点C，连接AC,BC，可以将凸变形分成三份,中间是一个三角形，左右两边还是凸边形
- 设问题的解为f(n)，n表示顶点数，那么f(n)=f(2)*f(n-1)+f(3)*f(n-2)+……+f(n-2)*f(3)+f(n-1)*f(2)。
- 其中，f(2)*f(n-1)表示：三个相邻的顶点构成一个三角形，另外两个部分的顶点数分别为2（一条直线两个点）和n-1。
- 其中，f(3)*f(n-2)表示：将凸多边形分为三个部分，左右两边分别是一个有3个顶点的三角形和一个有n-2个顶点的多边形。
- 设f(2) = 1，那么f(3) = 1, f(4) = 2, f(5) = 5。结合递推式，不难发现f(n) 等于h(n-2)，其解等于第n-2个卡特兰数（可以想象成有两个顶点无法连接）
其解为$\frac{C_{2n-4}^{n-2}}{n-1}$
6.圆上n条线段
问题描述：在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？
思路：
- 以某个点为基准，记编号为0，则与其相连的点的编号一定是奇数，否则会多余出来一个点
- 连接两点，可以将圆分成两部分，再将左右两部分分别连接两点（递归思想）
- 设问题的解f(n)，那么f(n) = f(0)*f(n-1) + f(1)*f(n-2) + f(2)*f(n-3) + …+f(n-2)*f(1) + f(n-1)*f(0)
- f(0)*f(n-1)表示编号0的点与编号1的点相连，此时位于它们右边的点的个数为0(可以连成0条线段)，而位于它们左边的点为2n-2（可以连成n-1条线段）。依次类推
- 令f(0) = 1, f(1) = 1, f(2) = 2，不难发现f(n)=h(n)，其解等于第n个卡特兰数
其解为$\frac{C_{2n}^{n}}{n+1}$
7.单调路径
问题描述：一位大城市的律师在他住所以北n个街区和以东n个街区处工作，每天他走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
思路：
- 假设E表示向东走，N表示向北走
- 显然，任意前缀中E的个数不小于N的个数
- 那问题可以转换成：给定一个2n长的EN序列，要求任意前缀中E的个数不小于N的个数，问有多少种序列
- 易得，其解和进出栈问题如出一辙，其解等于第n个卡特兰数
其解为$\frac{C_{2n}^{n}}{n+1}$
8.填充阶梯图形
问题描述：用n个长方形填充一个高度为n的阶梯状图形的方法个数？
思路：
- 把高度为n-1的阶梯状图形，塞进高度为n的阶梯状图形，把高度为n的阶梯状图形分为几个部分。
- 设问题的解f(n)，其中n表示高度为n的阶梯状图形或n个长方形。
- f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=5。
- f(0)*f(2)表示：高度为3的阶梯状图形含有这两个部分，一个部分是高度为2的阶梯状图形，另外一个部分是一边为3一边为1的长方形。
- f(1)*f(1)表示：高度为3的阶梯状图形含有这两个部分，都是高度为1的阶梯状图形。
- 结合递推式，不难发现f(n) 等于h(n)，其解等于第n个卡特兰数
其解为$\frac{C_{2n}^{n}}{n+1}$
9.排队问题
问题描述：2n个高矮不同的人排成两队，每队n个人，要求第二排的第i个人比第一排的第i个人高，问有多少种排队方式
思路：
- 高矮是相对的，先排成一长队
- 每一个高的都有一个矮的与之对应
- 问题即转化成进出栈问题，高的进第二排，矮的进第一排
- 任意前缀和不小于0，其解为第n个卡特兰数
其解为$\frac{C_{2n}^{n}}{n+1}$
剩下问题：
- 一个汽车队在狭窄的路面上行驶，不得超车，但可以进入一个死胡同去加油，然后再插队行驶，共有n辆汽车，问共有多少种不同的方式使得车队开出城去？
- 饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？
- 其解都等于第n个卡特兰数
其解都是$\frac{C_{2n}^{n}}{n+1}$
参考博客：
Sherry_Yue