卡特兰数是个好东西
求法#
1.$f(n)=\sum_{i=0}^{n-1}f(i)\cdot f(n-1-i)$
2.$f(n)=\frac{(4n-2)\cdot f(n-1)}{n+1}$
3.$f(n)=\frac{C_{2n}^{n}}{n+1}$
应用#
-
n 个节点的二叉树形态数
-
n 个元素的入栈、出栈的序列数
合法的出入栈序列：序列的任意前缀中，
入栈次数>=出栈次数 -
通过连接顶点把
(n+2)条边的凸多边形分割成三角形 -
几乎所有卡特兰数的问题都可以转化为 “完成 n 步 k1 操作和 n 步 k2 操作，其中要求 k1 操作次数始终大于 k2 次数”
实际做题过程#
大佬们都是证明这道题是卡特兰数。
而作为一个蒟蒻，我也就只能算出前三项（1,2,5），然后
“大胆而合理地外推”——hqx 大佬
"你应该在前面加一个像伽利略一样"——hqx 大佬