跳转至

卡特兰数

Catalan 数列

以下问题属于 Catalan 数列:

  1. 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票,另外 n 人只有 10 元钞票,剧院无其它钞票,问有多少中方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零?
  2. 一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
  3. 在圆上选择 2n 个点, 将这些点成对连接起来使得所得到的 n 条线段不相交的方法数?
  4. 对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数?
  5. 一个栈 (无穷大) 的进栈序列为 1,2,3, \cdots ,n 有多少个不同的出栈序列?
  6. n 个结点可够造多少个不同的二叉树?
  7. n 个不同的数依次进栈,求不同的出栈结果的种数?
  8. n +1 n -1 构成 2n a_1,a_2, \cdots ,a_{2n} ,其部分和满足 a_1+a_2+ \cdots +a_k>=0(k=1,2,3, \cdots ,2n) 对与 n 该数列为?

其对应的序列为:

H_0 H_1 H_2 H_3 H_4 H_5 H_6 ...
1 1 2 5 14 42 132 ...

(Catalan 数列)

该递推关系的解为:

H_n=\frac{C_{2n}^{n}}{n+1}(n=1,2,3,\cdots)

评论