做初赛题，回顾到以前学的一些知识，发现还有其他广泛的应用，所以在此记录并当作复习，若有不当之处，随时欢迎读者斧正。

Catalan

卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名

原理（摘自百度百科）

设h(n)为Catalan数的第n+1项，令h(0)=1,h(1)=1，Catalan数满足递推式
h(n)= h(0)h(n-1)+h(1)h(n-2) + … + h(n-1)h(0) (n>=2)
例如：h(2)=h(0)h(1)+h(1)h(0)=11+11=2
$\quad\quad$ h(3)=h(0)h(2)+h(1)h(1)+h(2)h(0)=12+11+21=5
另类递推式：
$\quad\quad$ h(n)=h(n-1)(4n-2)/(n+1)
递推关系的解为：
$\quad\quad$ h(n)=C(2n,n)/(n+1) (n=0,1,2,…)
递推关系的另类解为：
$\quad\quad$ h(n)=C(2n,n)-C(2n,n-1)(n=0,1,2,…)

应用

(1)凸n边形的三角划分方案数

笔者第一次接触卡特兰数是一道关于凸多边形的三角形划分问题，题目很容易懂：给出一个凸n边形，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。输入n，求不同划分的方案数f(n)
我初次尝试时，试着找规律，结果~~花式凉凉~~ ，老师第一次讲，听得云里雾里，回顾几次后，到觉得有点意思。

现在，读者请见下图：
卡特兰数 Catalan
一个凸n边形，两处标有省略号的地方表示省略的边，即顶点2到顶点i之间还有 i-2+1 条边，另一处同理。现在如果不知道卡特兰数的同学是不是无从下手，别慌，问题不大。因为凸n边形的任意一条边必定属于某一个三角形，所以我们以某一条边为基准,此图以顶点1和顶点n为基准。我们任意取一个点i使得1,n, i构成一个三角形，连接1-i,n-i.
见下图：
卡特兰数 Catalan
如图所示，凸n变形变为了一个由一个三角形，一个凸i变形和一个凸n-i+1边形，构成的图形，即题目中的定义，则此时凸n边形的不同划分方案数就根据乘法原理，由凸i变形和凸n-i边形决定，即 $f(i)\times f[n-i+1]$ ，在考虑，如果我不取点i为与点1和点n构成三角形，那么i+1呢？i+2呢？ $···$ ，选取不同的点之后便会有 $f(i+1)\times f[n-(i+1)+1],$ $\,\,f(i+2)\times f[n-(i+2)+1]···$ ，取不同的点与点1，点n划分后都可以的都划分凸n边形的划分方案，那加起来，不就是凸n边形的划分方案数了吗？即：
$f(n)=f(2)f(n-2+1)+f(3)f(n-3+1)+……+f(n-1)f(2)$
$\quad\quad\,\,=h(n-2)$
因为1,n, i三点要构成三角形，所以不能点i不能去点1和点n,而我们定义f(2)=1,f(3)=1

此处f(2)=1和f(3)=1的具体缘由须参考详尽的“卡特兰数”，也许可从凸四边形f(4)=f(2)f(3)+ f(3)f(2)=2×f(3)f(2)倒推，四边形的划分方案不用规律推导都可以知道是2，那么2×f(3)f(2)=2，则f(3)f(2)=1，又f(2)和f(3)若存在的话一定是整数，则f(2)=1，f(3)=1

(2)括号化

$P=a_1×a_2×a_3×……×a_n$ ，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
分析:将 $a_1看作一个整体，剩下n-1个数为一个整体，划分方案数：f(0)f(n-1)$ ,此处一个数打括号无意义，视作f(0),而且根据标准卡特兰数的定义f(0)=f(1)=1,所以f(1)f(n-1)可视作f(0)f(n-1)
将 $a_1，a_2看作一个整体，剩下n-2个数为一个整体，划分方案数：f(1)f(n-2)$
$······$
将 $a_1，a_2···a_{n-1}看作一个整体，剩下1个数为一个整体，划分方案数：f(n-1)f(0)$
即
$h(n)=\sum_{i=0}^{n-1}h(i)h(n-i-1)$
得证

(3)给定节点组成二叉搜索树

给定N个节点，能构成多少种不同的二叉搜索树？
分析：这个比较好理解，对于根节点，他的左子树和右子数的f(left) $\times$ f(right)就是当左子树有left个结点，右子树有right个结点时的组成方案，当左右结点不同时，乘积相加即可。PS：根节点要算一个节点，所以左右子树结点数相加等于n-1
$h(n)=\sum_{i=0}^{n-1}h(i)h(n-i-1)$

(4)n对括号正确匹配数目

给定n对括号，求括号正确配对的字符串数，例如：
0对括号：[空序列] 1种可能即f(0)=1
1对括号：() 1种可能
2对括号：()() (()) 2种可能
3对括号：((())) ()(()) ()()() (())() (()()) 5种可能
考虑n对括号时的任意一种配对方案，最后一个右括号有唯一的与之匹配的左括号，于是有唯一的表示A(B)，其中A和B也是合法的括号匹配序列
笔者看 $A(B)$ 这个式子时愣了很久，仔细想一下高亮部分才反应过来，’(‘是与最后一个’)'相匹配的左括号，两个括号将原序列划分成了两个相对独立的序列A和B，那么A的正确匹配数目与B的正确匹配数目相乘，不就正好与二叉搜索树组合时的左右子树方案数相乘神似吗？所以，答案自然就跟二叉搜索树的结果一样了，Catalan数参上：
$h(n)=\sum_{i=0}^{n-1}h(i)h(n-i-1)$

(5)出栈次序

一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

分析一：

设f(n)=序列个数为n的出栈序列种数
暂时写不动了，改天再补洞

卡特兰数 Catalan