加泰罗尼亚数字出现在哪里？
-给定括号对数的psp数量
-给定叶子数的二叉树的数量
-n*n方格中从左下角到右上角不碰到对角线的路径数
-n边形分成三角形的次数
怎么算？1) 第n个加泰罗尼亚数字的公式：
2)
•让我们有一个长度为 2n 的 PSS
•显然它以左大括号开头
•所以，假设 P = (A)B，其中 A 和 B –还有psp（另外，A和B可以为空）
•如果A的长度=2k，那么序列A可以用Ck种方式组合
•那么B的长度=2(n – k - 1)，B可以用Cn-k-1种方式组合
•我们看到 dp 的公式：Cn = sum(Ck * Cn-k-1) for all k <;
使用的材料：