跳转至

Catalan 数列

Catalan 数列 H_n 可以应用于以下问题：

  • 有 \(2n\) 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 \(n\) 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
  • 有一个大小为 \(n\times n\) 的方格图左下角为 \((0, 0)\) 右上角为 \((n, n)\)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 \(y=x\) 上方（但可以触碰）的情况下到达右上角有多少可能的路径？
  • 在圆上选择 \(2n\) 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
  • 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
  • 一个栈（无穷大）的进栈序列为 \(1,2,3, \cdots ,n\) 有多少个不同的出栈序列？
  • \(n\) 个结点可构造多少个不同的二叉树？
  • 由 \(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)\)，有多少个满足条件的数列？

$$ 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 = \frac{C^n_{2n}}{n+1} \]

例题

【例题】栈的问题

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
const int N = 20;

long long n, pre;

int main(){

    cin >> n;
    pre = 1;
    for(int i = 1; i <= n; i++){
        pre = pre * (4 * i - 2) / (i + 1);
    }
    cout << pre << endl;

    return 0;
}