原理
令 h(0) = 1, h(1) = 1, catalan数满足
h(n)= h(0)×h(n-1)+h(1)×h(n-2) + … + h(n-1)×h(0) (n>=2)
通项公式
h(n) = C(2n, n) / (n + 1) = (2n)! / ((n + 1)! × n!)
##应用
括号化
n组括号的合法运算式的个数
如((())) ()(()) ()()() (())() (()())
出栈次序
感觉此应用和括号化类似。
省去不表，详情见上篇博文。
构建二叉树和满二叉树
h(n)表示n个节点构建二叉树的方案数
h(n)表示2n + 1个节点构建**满二叉树的方案数
凸多边形的划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。