卡特兰数

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 \geq 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{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})

关于 Catalan 数的常见公式:

H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}
H_n = \frac{H_{n-1} (4n-2)}{n+1}
H_n = \binom{2n}{n} - \binom{2n}{n-1}

路径计数问题

非降路径是指只能向上或向右走的路径。

  1. (0,0) (m,n) 的非降路径数等于 m 个 x 和 n 个 y 的排列数,即 {n + m \choose m}

  2. (0,0) (n,n) 的除端点外不接触直线 y=x 的非降路径数:

    先考虑 y=x 下方的路径,都是从 (0, 0) 出发,经过 (1, 0) (n, n-1) (n,n) ,可以看做是 (1,0) (n,n-1) 不接触 y=x 的非降路径数。

    所有的的非降路径有 {2n-2 \choose n-1} 条。对于这里面任意一条接触了 y=x 的路径,可以把它最后离开这条线的点到 (1,0) 之间的部分关于 y=x 对称变换,就得到从 (0,1) (n,n-1) 的一条非降路径。反之也成立。从而 y=x 下方的非降路径数是 {2n-2 \choose n-1} - {2n-2 \choose n} 。根据对称性可知所求答案为 2{2n-2 \choose n-1} - 2{2n-2 \choose n}

  3. (0,0) (n,n) 的除端点外不穿过直线 y=x 的非降路径数:

    用类似的方法可以得到: \frac{2}{n+1} {2n \choose n}


评论