【文件属性】：
文件名称：« ACM模板收集Let the Balloon Rise » Catalan数
文件大小：3KB
文件格式：TXT
更新时间：2013-08-29 10:31:38
Catalan数
« ACM模板收集Let the Balloon Rise »
Catalan数
Catalan numbers 的公式：
Cn=C(2n,n)/(n+1);1
Cn+1=C(2n+2,n+1)/(n+2);2
由1和2推出
Cn/C(n+1)=(n+2)/(4n+2);
而且，对于一个具有n个节点的数的形态的数目 也是同样。。
下面来自：http://acm.hdu.edu.cn/forum/read.php?tid=528&keyword=Catalan|numbers
catalan numbers可以用在以下方面：
1. the number of ways a polygon with n+2 sides can be cut into n triangles
2.the number of ways in which parentheses can be placed in a sequence of numbers to be multiplied, two at a time;
3.the number of rooted, trivalent trees with n+1 nodes; (hdu 1131)
4.the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal.
在这里记下一个重要的结论,一个生成树的有n各节点 可以用 n^(n-2)中生成树.