内容部分来自以下博客:
Cyberspace_TechNode
邀月独斟
一个大叔
表示感谢!
Catalan数的引入:
- 一个长度为2N的序列,里面有N个+1,N个-1 它的任意前缀和均非负,给定N,求有多少个这样的序列
- 2n个人排队买票,其中n个人持50元,n个人持100元。每张票50元,且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序,不至于使售票处找不开钱
可以发现这两个问题的本质是一样的(括号匹配问题),它们的答案都是卡特兰数
定义:令h(0)=1,h(1)=1,Catalan数满足递归式:h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)
当然卡特兰数的表示形式很多:
另类递推式:h(n)=h(n-1)*(4*n-2)/(n+1)
递推关系的解为:h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
递推关系的另类解为:h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...) ---> 对应多重集合的排列
可以解决的问题:(待续...)
- 入栈出栈问题
- 矩阵连乘问题
- 街区对角线问题
- 圆上点对互连问题
- 多边形划分问题
- 二叉树构造问题
- n层阶梯切割问题
- 填数问题/照相排队问题
- ...