要使所有的括号合法，实际上就是在每一个前缀中左括号的数量都不少于右括号的数量
将左括号看做\(1\)，右括号看做\(0\)，这题又和上面那题一模一样了
有一个栈，我们有\(2n\)次操作，\(n\)次进栈，\(n\)次出栈，问有多少中合法的进出栈序列
合法的序列个数为\(C_{2n}^{n}-C_{2n}^{n-1}\)
要使序列合法，在任何一个前缀中进栈次数都不能少于出栈次数\(\ldots\)
后面就不用我说了吧，和上面的问题又是一模一样的了
一个长度为\(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\)阶矩形有多少种矩形划分
答案仍然是卡特兰数列
我们考虑阶梯的每个角