引入
- \(n\) 个节点的二叉树个数。
- 长度为 \(2n\) 的合法括号序列数量。
不加说明的给出结论：上面两个问题的答案均为卡特兰数列 \(H\) 的第 \(n\) 项，\(H_n\)。
暴力 DP 理解
第一个问题
设 DP 状态 \(f(i)\) 为 \(i\) 个节点的二叉树个数。
求 \(f(i)\) 时，枚举左儿子节点数量 \(j\)、得到右儿子节点数量 \(i-1-j\)。
两部分方案数 \(f(j)\)、\(f(i-1-j)\) 乘起来得到这种情况下的方案数。
\[f(i)= \begin{cases} 1 & i=0\\ \sum\limits_{j=0}^{i-1}f(j)f(i-1-j) &i > 0 \end{cases} \]上述转移即为定义 Catalan 数列的递推关系（虽然一开始求解的问题不是此问题）。
如果要通过此方法求出卡特兰数列的第 \(n\) 项，预处理复杂度 \(\mathcal O(n^2)\)，查询复杂度 \(\mathcal O(1)\)。
第二个问题
通过一些括号序列的知识，该问题等价于将 ( 视为 \(1\)，) 视为 \(-1\)，同时每个位置的前缀和 \(\ge 0\) 的序列的个数。
那么可以设 DP 状态 \(f(i,j)\) 表示，已经填了 \(i\) 个数，\(i\) 个数总和为 \(j\) 的序列个数。
容易得到转移式：
\[f(i,j)= \begin{cases} f(i-1,j+1)& j = 0 \\ f(i-1,j-1)+f(i-1,j+1) & 0 < j \le i \\ 0 &\text{otherwise.} \end{cases} \]回到原问题上，方案数为 \(f(2n,0)\)。
预处理复杂度 \(\mathcal O(n^2)\)，查询复杂度 \(\mathcal O(1)\)。
证明它是 Catalan
根据第一个问题的引入，写出 Catalan 数的定义递推公式
\[H_n= \begin{cases} 1 & n = 0\\ \sum\limits_{i=1}^{n}H_{i-1}H_{n-i} & n > 0 \end{cases} \]Call Back
而对于第二个问题如何证明它也是 Catalan 数呢？
考虑得到新的转移式。
设 \(f(n)\) 为长度为 \(2n\) 的合法括号序列数量。
枚举 \(i\)，统计满足 \(1\sim 2i\) 为合法括号序列 的 最短前缀 的括号序列数量。划分为两个子问题。
-
\(1\sim 2i\) 为合法括号序列，同时需要保证 \(1\sim 2i\) 不存在更短的前缀，满足其为合法括号序列。
那么这部分括号序列第 \(1\) 位一定为
(，第 \(2i\) 位一定)。（充要条件）这部分方案数为 \(f(i-1)\)。
-
\(2i+1\sim 2n\) 为合法括号序列，方案数为 \(f(n-i)\)。
这样就能够得到和 Catalan 数列的一样的递推公式。即能证明第二问题的答案也为 Catalan 数。
卡特兰数列可以应用的问题
以下问题的答案均为 \(H_n\)。
-
凸 \(n+2\) 边形的三角形划分方案数。
最早被发现答案为 Catalan 数的问题。
写出该问题的递推式即可证明其为 Catalan 数。
-
\(n\) 个节点的二叉树个数。
引入的问题。
-
长度为 \(2n\) 的合法括号序列数量。
引入的问题。
-
给定圆上 \(2n\) 个点，将这些点成对连接所得到的 \(n\) 条线段不相交的方案数。
证明：写出递推式！
-
\(n\) 个矩形填充长宽为 \(n\) 的阶梯图形的方案数。
枚举第 \(n\) 列的矩形的长度 \(h\)（它的形状只能为 \(1\times h\)）能够转成求两个子阶梯的填充方案数。
写出递推式后即能证明其为 Catalan 数。
-
长度为 \(2n\) 的排列 \(p\)，满足 \(p_1 < p_3 < \dots < p_{2n-1}\)；\(p_2 < p_4 < \dots < p_{2n}\) ；\(p_{2i-1}<p_{2i}\) 的个数。
首先需要观察出 \(p_{2i}\) 为 \(1\sim 2i\) 的最大值。
将 \(1\sim 2n\) 从小到大分成奇偶位填入。
由于上面的性质，填数 \(i\) 时，需要保证每次填完 \(i\) 后，填入奇数位的数不少于填入偶数位的数。
等价于合法括号序列方案数，答案即为 \(H_n\)。
有很多能够轻易转化为合法括号序列方案数的问题就不写了。
背下 Catalan 数列有助于找规律。推导尽量往经典模型上靠。不拘泥于一种模型。
| \(H_0\) | \(H_1\) | \(H_2\) | \(H_3\) | \(H_4\) | \(H_5\) | \(H_6\) | \(\dots\) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 5 | 14 | 42 | 132 | \(\dots\) |
通项 / 快速计算
\(\mathcal O(n^2)\) 预处理太慢了！考虑更快的方法！
考虑长度为 \(2n\) 的序列 \(a\)，\(a_i\) 为 \(1\) 或 \(-1\)，同时 \(\forall i\in [1,n]\)，\(\sum\limits_{j=1}^{i}a_j\ge 0\)。\(H_n\) 即为满足条件的 \(a\) 的个数。
正难则反。首先 \(a\) 中有 \(n\) 个 \(1\)，\(n\) 个 \(-1\)，方案数为 \(\binom {2n} n\)。考虑在这样的 \(a\) 中不满足条件的 \(a\) 的个数。
找到最小的满足 \(\sum\limits_{j=1}^{i}a_j<0\) 的 \(i\)（既然不满足条件，那么一定存在这样的 \(i\)）。
转化：将 \([i+1,n]\) 全部取相反数，得到序列 \(a'\)。
序列 \(a'\) 会满足 \(\sum\limits_{i=1}^{n}a'_i=-2\)。\(a'\) 中有 \(n-1\) 个 \(1\)，\(n+1\) 个 \(-1\)。
现在证明：\(a'\) 数量与不满足条件的 \(a\) 序列数量相同。
-
每个不满足条件的 \(a\) 能够对应到不同的 \(a'\)。考虑构造 \(a'\) 的过程即能说明。（充分性）
-
每个 \(a'\) 能够对应到不满足条件的 \(a\)。
找到最小的满足 \(\sum\limits_{j=1}^{i}a'_j<0\) 的 \(i\)（一定存在，\(a'\) 总和 \(<0\)），将 \([i+1,n]\) 取反即能够对应到不满足条件的 \(a\)。
根据上述构造，\(a'\) 对应到的 \(a\) 是两两不同的，得证。（必要性）
那么可以得到：
\[H_n=\binom {2n} n-\binom {2n}{n-1}\\ H_n=\binom {2n} n-\binom {2n}{n+1}\\ H_n=\dfrac{\binom{2n}{n}}{n+1}\\ H_n=\dfrac{2n!}{(n+1)!n!} \]于是当模数为质数时，能够 \(\mathcal O(n)\) 预处理阶乘、阶乘逆元 \(\mathcal O(1)\) 计算。
标签：括号,2i,Catalan,序列,mathcal,2n,卡特兰,小记 From： https://www.cnblogs.com/sprads/p/18013531