卡特兰数可以解决一些计数问题，还是挺常用的。
前几项是 \(1,1,2,5,14,42,132,\dots\)
下文用 \(C_n\) 表示卡特兰数第 \(n\) 项，\(n\) 从 \(0\) 开始。
公式
如果不记得通项，可以用下面的一些经典模型推导出来。
通项
\[C_n=\binom{2n}{n}-\binom{2n}{n-1} \]也可以写成
\[C_n=\frac{\binom{2n}{n}}{n+1} \]其它公式
如果见到了下面这两种，要记得是卡特兰数，可以 \(O(1)\) 计算。
\[C_n=\sum\limits_{i=1}^n C_{i-1}C_{n-i} \]\[C_n=\frac{4n-2}{n+1}C_{n-1} \]经典问题
网格路径问题
从 \((0,0)\) 走到 \((n,n)\)，只能向右或向上走，不能穿过 \(y=x\) 的路径条数为 \(C_n\)。
如果不考虑“不穿过”的限制，相当于在 \(2n\) 个点选择 \(n\) 次向右（或向上），这是个经典问题，方案数为 \(\binom{2n}{n}\)。现在只需要减去不合法的方案数。
考虑一条不合法的路径，穿过 \(y=x\) 相当于在某个点触碰到了 \(y=x+1\)。将这个触碰点之后的右、上移动交换，那么最后一定走到 \((n-1,n+1)\)，因此不合法路径的数量为 \(\binom{2n}{n-1}\)。
那么方案为 \(\binom{2n}{n}-\binom{2n}{n-1}\)，这是卡特兰数。
括号序列（±1序列）问题
这两个问题本质上是一样的。
括号序列：求有多少长度为 \(2n\) 的合法括号序列。
±1序列：将 \(n\) 个 \(1\) 和 \(n\) 个 \(-1\) 排列，使得任意前缀之和 \(\ge 0\)。
以±1序列为例，总数是 \(\binom{2n}{n}\)，只需要减去不合法数量。考虑一种不合法排列，必然有一个位置 \(p\) 的前缀和 \(=-1\)，则 \(1\sim p\) 中 \(-1\) 比 \(1\) 多一个， \(p+1\sim n\) 中 \(1\) 比 \(-1\) 多一个。现在将 \(p+1\sim n\) 的数字取反，整个序列就变成由 \(n+1\) 个 \(1\) 和 \(n-1\) 个 \(-1\) 组成的序列，方案数为 \(\binom{2n}{n-1}\)。
最终还是 \(\binom{2n}{n}-\binom{2n}{n-1}\)，是卡特兰数。
进出栈问题
\(1,2,3,\dots,n\) 依次进栈，求出栈序列的数量。
枚举 \(1\) 的进出栈时间，整个过程可以表示为
- \(1\) 进栈。
- \(2\sim k\) 全部进栈并出栈。
- \(1\) 出栈。
- \(k+1\sim n\) 全部进栈并出栈。
设 \(f_n\) 表示 \(n\) 个不同的数的出栈序列数量，那么
\[f_n=\sum\limits_{k=1}^{n}f_kf_{n-k} \]这是卡特兰数的一个公式。
二叉树形态问题
求 \(n\) 个点的二叉树有多少种形态。
设 \(f_n\) 表示 \(n\) 个点二叉树的形态数量，将根+左子树看成一个部分，右子树看做另一个部分，那么可以得到转移
\[f_n=\sum\limits_{k=1}^{n}f_{k}f_{n-k} \]还是卡特兰数。
变式及应用
将 \(2n\) 个不同的数分为两个大小为 \(n\) 的递增数列 \(a,b\)，求使得 \(\forall i,a_i<b_i\) 的方案数。
考虑这 \(2n\) 个数的一个排列，我们将其中 \(a\) 中的数替换为 “\((\)”，\(b\) 中的数替换为 “\()\)”，那么 \(a,b\) 是合法划分当且仅当括号序列合法。所以方案数就是卡特兰数 \(C_n\)。
如何理解这个转化呢？对于转化后的括号序列，对于从左到右的每一个左括号，将其看做 \(a_1,a_2,a_3\dots\)，与之匹配的右括号看做 \(b_1,b_2,b_3,\dots\)。那么显然只有合法的括号序列对答案有贡献，并且不同的合法括号序列对应不同的划分方案。
标签：入门,卡特兰,括号,序列,2n,合法,binom From： https://www.cnblogs.com/hzy1/p/16869605.html