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