Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

卡特兰数是个好东西

求法

1.f(n)=i=0n1f(i)f(n1i)f(n)=\sum_{i=0}^{n-1}f(i)\cdot f(n-1-i)
2.f(n)=(4n2)f(n1)n+1f(n)=\frac{(4n-2)\cdot f(n-1)}{n+1}
3.f(n)=C2nnn+1f(n)=\frac{C_{2n}^{n}}{n+1}

应用

  • n个节点的二叉树形态数

  • n个元素的入栈、出栈的序列数

    合法的出入栈序列:序列的任意前缀中,入栈次数>=出栈次数

  • 通过连接顶点把(n+2)条边的凸多边形分割成三角形

  • 几乎所有卡特兰数的问题都可以转化为“完成n步k1操作和n步k2操作,其中要求k1操作次数始终大于k2次数”

实际做题过程

大佬们都是证明这道题是卡特兰数。

而作为一个蒟蒻,我也就只能算出前三项(1,2,5),然后

“大胆而合理地外推”——hqx大佬

“你应该在前面加一个像伽利略一样”——hqx大佬

评论