- 名字来源比利时数学家卡塔兰。
卡塔兰：Catalan
-
数列
满足
-
通项：
- 给定n个节点，能构成的二叉搜索树个数为Cn。
对于n个节点的最大节点M，所有二叉搜索树必满足
- M无右子树
- M不是左子节点
- 存在数i，使得M的左子树中的所有节点大于i，且M的余树的所有节点小于i
- 通过互不相交的对角线把凸n边形划分成为若干个三角形的划分法为Cn-2。
取凸n边形的一边做三角形，必将依次遍历余下n-2个顶点，每次将凸n边形划分为三部分，三部分的划分为三角形的划分法数依次为Ci，1，Cn-3-i
- n个不同的数依次进栈，则其不同的出栈序列有Cn种。
对于最后出栈的数M，若其是第i个进栈的数，则前i-1个数必在M进栈前出栈，而后n-i个数的进出栈顺序与前i个数无关。
- n个1和n个-1组成数列，那么满足部分和恒非负的不同数列有Cn个。
必存在某个部分和为0，取第一个为0的部分和Sm，易知
网友评论