卡特兰数是组合数学中的一种常见数列
它的前几项为:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670,129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452
递归公式1
f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)
递归公式2
f(n)=\frac{f(n-1)*(4*n-2)}{n+1}
组合公式1
f(n)=\frac{C_{2n}^n}{n+1}
组合公式2
f(n)=C_{2n}^n-C_{2*n}^{n-1}
这四个公式了解即可:joy:(众人:*******:angry:)
最后一个,最重要的公式,必须要掌握的公式!!
递推公式
f[n]=\sum_{i=0}^{n-1}f[i]*f[n-i-1]
一般在做题的时候,都是利用这个公式进行递推
不会:stuck_out_tongue_closed_eyes:。(众人:那你在这瞎bb啥。:triumph:)
这个东西的证明我确实不会
不过我在这里教大家一种非常简单易懂的记忆方法,
记f[n]为卡特兰数的第n项
首先你要明白一件事情
一棵n个节点的二叉树的形态总数,就是卡特兰数的第n项
对于一棵二叉树,递归的考虑
一棵只有一个节点的二叉树只有一种形态
对于不是一个节点的二叉树,按照他的左右孩子进行讨论
设它的左孩子有i个节点,那么它的形态数为f[i]
那么它的右孩子有n-i-1个节点,那么它的形态数为f[n-i-1]
又因为每一个节点都可以作为根节点
所以不难得到递推式
f[n]=\sum_{i=0}^{n-1}f[i]*f[n-i-1]
都是裸题我就不细讲了
http://www.cnblogs.com/zwfymqz/p/7725346.html
http://www.cnblogs.com/zwfymqz/p/7725386.html
卡特兰数是一种常见的数列
需要每一位选手掌握它的递推式
卡特兰数一般不会单独出现,往往会出现在一些题目的部分分中,如2017某省省选(具体忘记了。)
在考场上,要证明一个东西是卡特兰数是非常困难的
自己手玩点小数据,只要前几项吻合,那一般就是卡特兰数啦