内容部分来自以下博客：
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层阶梯切割问题
- 填数问题/照相排队问题
- ...