Catalan 数模型总结 & （或许会有）习题分析
Catalan 式子
\(Cat_n=\binom {2n} {n}-\binom {2n}{n-1}\)
\(Cat_n=\binom {2n} {n}/(n+1)\)。
\(Cat_n=Cat_{n-1}*\frac {4n-2} {n+1}\)
求Catalan（组合）数的方法
- \(\mathcal{O}(n^2)+\mathcal{O}(1)\) 暴力转移。
- \(\mathcal{O}(n)+\mathcal{O}(1)\) 组合数算。
- \(\mathcal{O}(0)+\mathcal{O}(\sqrt n)\) 分解质因数算。
- \(\mathcal{O}(n)+\mathcal{O}(1)\) 用 Catalan 数的递推公式算。
\(n\) 边形的三角剖分
凸 \(n+2\) 边形进行三角剖分的方案数是 \(Cat_n\)。证明懒得写了，不难。
括号匹配
\(n\) 个左括号和 \(n\) 个右括号匹配的方案数是 \(Cat_n\)。
二维路径
\((0,0)\) 走到 \((n,n)\)，每次只能向右或向上走，不能碰到对角线的方案数为 \(Cat_n\)。不能超过对角线的方案数为 \(Cat_{n-1}\)。证明可以看此题：abc205e。事实上，Catalan 数的通项的证明之一就是这个。这也是个常见的 trick。
圆周染色
将圆周上 \(2n+1\) 个选择 \(n\) 个点染色，方案数为 \(Cat_n\)。
我目前会的证明只是简单的：\(ans=\binom {2n+1} {n}/(2n+1)=\binom {2n}{n}/(n+1)=Cat_n\)。
弦互不相交
将圆周上的 \(2n\) 个点两两连接，方案数为 \(Cat_n\)。
PF：还是老套路，钦定 \(1\) 与那个点连边。\(dp_{i}=\sum_{j=2}^{2n}dp_{j-2}\times dp_{i-j}\)。考虑这里下标为奇数的 dp 值为 \(0\)。所以这里参与转移的 \(i,j\) 其实都是偶数。那考虑将 \(i,j\) 全都除以 \(2\)。则 \(dp_i=\sum_{j=1}^ndp_{j-1}\times dp_{i-j}\)，即证。
令 \(n\) 元有序数组的集
排列问题
我们有长度分别为 \(n\) 单调递增的数列 \(\{a\}\{b\}\)，打乱重排为长度为 \(2n\) 的全排列。满足 \(\forall a_i>b_i\) 的方案数为 \(Cat_n\)。
PF：将全排列中属于两个不同集合的数染成不同的颜色，要满足：\(\forall pre_{a_i}\le pre_{b_i}\)，即证。
投票记录
夏皮罗曲线
咕。
p.s. 此篇博客借鉴于 link。