iPie

今天才知道Catalan数这个东西。。。汗～，赶紧在网上查了资料补补课。

令h(1)＝1,catalan数满足递归式：

h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)

即：

Catalan数的通项公式为：

该公式的推导过程可以看参考资料[2]的内容，在此不再累述。

我还看到有人争论Catalan数的通项公式应该是这样的：

其实这两个公式本质是一样的，公式（1）是以h(1)=1为起始项，而公式（2）是以h(0)=1为起始项。

关于Catalan数的应用可以参考这里。

这里举个应用Catalan数的例子：n个节点能组成多少种形态的二叉树？（注：每个节点相同；形态不同的左右子树对调后形成的二叉树算新的形态的二叉树）

可以分析，当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，则h(1)=1;

当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树，即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。这里h(0)表示空，所以只能算一种形态，即h(0)=1;

当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树，即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。

以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种，即符合Catalan数的定义，可直接利用通项公式(2)得出结果。

参考资料：
1.Catalan数，http://baike.baidu.com/view/1163998.htm
2.Catalan数的分析和应用，http://blog.csdn.net/dlyme/archive/2008/06/10/2532831.aspx