zcmimi's blog
avatar
zcmimi
2020-10-01 16:21:19
  • 本文总阅读量

定义

H_n = \begin{cases} \sum_{i=1}^n H_{i-1} H_{n-i} & n \ge 2 \\ 1 & n = 0, 1 \end{cases}

该递推关系的解为:

H_n = \frac{{2n\choose n}}{n+1}(n \ge 2)

常见公式:

H_n = \frac{H_{n-1} (4n-2)}{n+1}

H_n = {2n\choose n} - {2n\choose n-1}

卡特兰数列(下标从0开始):

1,1,2,5,14,42,132,\dots

卡特兰数问题

  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+1n-1构成2na_1,a_2, \cdots ,a_{2n},其部分和满足a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)对与n该数列为?

路径计数问题

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

  1. (0,0)(m,n)的非降路径数等于mxny的排列数,即{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\left[{2n-2\choose n-1} - {2n-2\choose n}\right]

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

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

卡特兰数
comment评论
Search
search