卡特兰数

   根源

   看到了zhihu上的东西：有一个大问题A，规模为n，要解决这个问题，可以用分治的思想，首先固定其中某一个元素，将剩下的n-1个元素拆分成两个小问题，这两个小问题的规模分别是(0,n-1) (1,n-2) (2,n-3) ... (n-1,0)，如二叉树计数，n个结点的二叉树，首先固定根节点，将剩下的n-1个结点拆分给左右子树；三角形划分问题，凸(n+2)边形可以划分为n个三角形，首先固定一条边（即一个三角形），这个三角形将这个(n+2)边形拆分成两个更小的多边形。

   数列前~n~項

   {1,1,2,5,14,42,132,429,1430,4862,16796,58786}

   数列の原理

   令h(0)=1,h(1)=1，Catalan数满足递推式

   h(n)=h(0)*h(n-1)+h(1)*h(n-2)+···+h(n-2)*h(1)+h(n-1)*h(0) （n>=2）

   令类递推式

　h(n)=h(n-1)*(4*n-2)/(n+1)

　递推关系的解为

   h(n)=C(2n,n)/(n+1) (n>=0)

   递推关系的另类解为

   h(n)=C(2n,n)-C(2n,n-1) (n>=0)

填几道题练手吧

   例題選ば

1、

卡特兰数

原文：http://www.cnblogs.com/keshuqi/p/6361740.html