卡特兰数 (Catalan)

卡特兰数:(是一个在计数问题中出现的数列)

一般项公式:

1. 卡特兰数 (Catalan)               2.  卡特兰数 (Catalan)

递归公式:

1. 卡特兰数 (Catalan) 

2. 卡特兰数 (Catalan)

注:全部可推导。

(性质:Cn为奇数时,必然出现在奇数项 2k-1。 (除去第 0 项))

应用举例:

1. 连乘的 n 个数加括号。 答案: Cn-1

2. 一个(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?  答案:Cn

引申1:入栈看作 1 操作, 出栈看作 0 操作,则整个序列入栈出栈后从左到右遍历 1 和 0 组成的序列,1 的个数总是不小于 0 的个数,且 1 和 0 各 n(入栈 n 次,出栈 n 次) 个。因此, n 个 1 和 n 个 0 组成的全部满足条件 1 出现次数不少于 0 的序列数为:  Cn

引申2: 将 1 看成 '(', 0 看成 ')', 则由 n 对 "()" 组成的有效序列 ['(' 在 ')' 之前] 个数为: Cn

3.  n 个结点的二叉树个数: Cn

4.  n+2边的凸多边形分三角形方法的个数: Cn

5.  平面上连接可以形成凸包的2n个点分成2个一组连成n条线段,两两线段之间不相交的情况总数是:Cn

上一篇:03 Django模型层: 常用(非常用)字段和参数


下一篇:深入理解BFC和外边距合并(Margin Collapse)