常见问题

1. 售票问题：2n 个人去看电影，n 个人手上有 5 元，另外 n 个人有 10 元，售票处没有零钱，问有多少种排队顺序可以使得 2n 个人顺利买到票？
2. 圆与弦问题：圆上有 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数
3. 合法栈序列问题：n 个元素合法入栈的合法序列数有多少种？
4. 二叉树种类数问题：n 个节点可以构造出多少个不同的二叉树？
5. 三角剖分问题：对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数
6. 非降路径计数问题：从 到 的除端点外不穿过（可接触） 的非降路径数

   Catalan 序列

   设 为 Catalan 数，，前几项依次为

递推求解公式：

排列组合公式直接求解：

1. 
2. ```cpp

include

using namespace std; int n; long long f[25];

int main() { f[0] = 1; cin >> n; for (int i = 1; i <= n; i++) f[i] = f[i - 1] (4 i - 2) / (i + 1); cout << f[n] << endl; return 0; } ```

路径规划问题

重点是 2 中对称变化部分，需要计算非法路径数，所以将路径的前半部分对称，正好等于 到 的路径数量。

参考资料

1. https://oi-wiki.org/math/combinatorics/catalan/