《算法》中的二叉查找树一节的一道习题。
N个元素组成的二叉树固定一个根节点，这个根节点的左右子树组合数为(0,n-1),(1,n-2),(2,n-3)...(n-1,0)，假设N个元素组成的二叉树种类为f[n]，则
f[n] = f[0]*f[n-1]+f[1]*f[n-2]+...+f[i]*f[n-1-i](i从0到n-1)
当只有一个节点时f[1]=1,当有两个节点时f[2]=2,假设当n=0时f[0]=1,由此可以得到归纳函数
f[0]=1;
f[1]=1; ... f[n]=f[0]*f[n-1]+f[1]*f[n-2]+...+f[i]*f[n-1-i](i的范围从0带n-1)
这个递推关系符合Catalan number的定义：http://en.wikipedia.org/wiki/Catalan_number
原文：http://www.cnblogs.com/elvalad/p/4141166.html