卡特兰数

• 名字来源比利时数学家卡塔兰。

  卡塔兰：Catalan

• 数列 满足
• 通项：
• 给定n个节点，能构成的二叉搜索树个数为C_n。

对于n个节点的最大节点M，所有二叉搜索树必满足

• M无右子树
• M不是左子节点
• 存在数i，使得M的左子树中的所有节点大于i，且M的余树的所有节点小于i
• 通过互不相交的对角线把凸n边形划分成为若干个三角形的划分法为C_n-2。

取凸n边形的一边做三角形，必将依次遍历余下n-2个顶点，每次将凸n边形划分为三部分，三部分的划分为三角形的划分法数依次为C_i，1，C_n-3-i

• n个不同的数依次进栈，则其不同的出栈序列有C_n种。

对于最后出栈的数M，若其是第i个进栈的数，则前i-1个数必在M进栈前出栈，而后n-i个数的进出栈顺序与前i个数无关。

• n个1和n个-1组成数列，那么满足部分和恒非负的不同数列有C_n个。

必存在某个部分和为0，取第一个为0的部分和S_m，易知