$CatalanNumbers$
卡特兰数是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图和比利时的数学家欧仁·查理·卡特兰的名字来命名.
前 \(10\) 项为：\(1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862\)
公式
\(tip:\) 在 \(n=17\) 时 \(Catalan\) 数就会超过 \(int\) 范围。
出栈问题
一个栈的入栈顺序为 \(1,2,3,\ldots ,n\) 时，出栈顺序有多少种?
栈中每个元素需要经历入栈出栈，所以会有 \(2n\) 个操作，记入栈为 \(+1\) ，出栈为 \(-1\) ，那么每个合法操作顺序每个前缀和必须 \(\ge0\) 。如果直接求显然不方便，那么正难则反。如果当前 \(n\) 非法，那么需要在所有的 \(C_{2n}^{n}\) 情况中，去掉 \(C_{2n}^{n+1}\) 个非法序列（因为非法序列相当于在 \(n+1\) 个位置放置 \(-1\) ，在 \(n-1\) 个位置放置 \(+1\) ）。\(C_{2n}^{n}-C_{2n}^{n+1}=\frac{C_{2n}^{n}}{n+1}\) 此时就得到了 \(Catalan\) 数。
括号问题
\(n\) 对括号能构成多少种合法序列？
很显然与出栈问题相同，答案就是 \(Catalan\) 数。
满二叉树问题
\(n+1\) 个节点可以构成多少种满二叉树？
对于每个节点要么子节点为空，要么同时存在两个节点，如果把左儿子看作 \(+1\) ， 右儿子看作 \(-1\) ，那么又与出栈问题相同。
凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数 \(n\)，求不同划分的方案数 \(f(n)\)。比如当 \(n=6\) 时，\(f(6)=14\)。
