记录一下两个结论。
- 有标号 \(n\) 边形的三角剖分数等于 \(B_{n-2}\)，其中 \(B\) 是卡特兰数。
证明：
考虑 DP，设 \(C_n\) 为有标号 \(n\) 边形的三角剖分数，考虑与 \(1\) 号点相连的最小的那条边 \((1,1+i)\)（若没有与 \(1\) 号点相连的边则钦定与 \(1\) 号点相连的最小的那条边为 \((1,n)\)），有：
\[C_n=\sum_{i=2}^{n-1} C_{i}C_{n-i+1} \]注意和式里面不是 \(C_{i+1}C_{n-i+1}\) 的原因是我们钦定了与 \(1\) 号点相连的最小的那条边为 \((1,1+i)\)，那么在这条边分割出的那个 \(i+1\) 边形中，\(1\) 需要满足没有出边，也就是说一定有边 \((2,1+i)\)，然后就转化为了 \(i\) 边形的三角剖分问题。
将这个式子稍作位移：
\[\begin{aligned} C_{n+2}&=\sum_{i=2}^{n+1}C_iC_{n-i+3}\\ &=\sum_{i=0}^{n-1}C_{i+2}C_{n-i+1} \end{aligned} \]令 \(B_n=C_{n+2}\)，发现就是卡特兰数的递推式：
\[B_n=\sum_{i=0}^{n-1}B_iB_{n-i-1} \]顺便说一下为啥这是卡特兰数的递推式：考虑枚举最后一次碰到 \(y=x\) 是位置 \((i,i)\)，然后就是从 \((i+1,i)\) 走到 \((n,n-1)\)，即为 \(B_{n-i-1}\)。
- \([x^n]B(x)^k\) 为从 \((0,0)\) 走到 \((n+k-1,n)\) 且不越过 \(y=x\) 的方案数。
证明是一个比较妙的组合意义。
首先 \([x^n]B(x)^k\) 相当于如下路径的方案数：这是一条 \(k\) 段的路径，每一段都是从 \((i,i)\) 走到 \((j,j)\)（\(i\leq j\)）。
然后我们考虑对这条路径做一个映射。先设这 \(k\) 段分别是 \((0,0)\to (p_1,p_1)\to (p_2,p_2)\to \cdots\to (p_{k-1},p_{k-1})\to (n,n)\)，然后把每一段在前面的路径的基础上向右偏移一位，就映射到了一条 \((0,0)\) 到 \((n+k-1,n)\) 且不越过 \(y=x\) 的路径。
然后证明每一条 \((0,0)\) 到 \((n+k-1,n)\) 且不越过 \(y=x\) 的路径都能一一对应回原来那条路径：我们先找到这条路径最后一次碰到 \(y=x\) 的位置 \((p_1,p_1)\)，再找到这条路径最后一次碰到 \(y=x-1\) 的位置 \((p_2+1,p_2)\)，……，再找到这条路径最后一次碰到 \(y=x-(k-2)\) 的位置 \((p_{k-1}+k-2,p_{k-1})\)。这样我们就得到了 \(p_1,\cdots,p_k\)，不难发现路径 \((0,0)\to (p_1,p_1)\to (p_2,p_2)\to \cdots\to (p_{k-1},p_{k-1})\to (n,n)\) 恰好就是映射回这条路径。
另外提一句，求出 \([x^n]B(x)^k\) 还可以用扩展拉格朗日反演。
标签：XSY3726,路径,三角,sum,边形,卡特兰,号点 From： https://www.cnblogs.com/ez-lcw/p/16841026.html