卡特兰数

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

公式

1
2
3
4

i64 ans = 1;
for (int i = 2 ; i <= n ; i++) {
    ans = ans * (4 * i - 2) / (i + 1);
}

1
2
3

{ 组合数模版 }
using Combination::C;
i64 ans = (C(2*n,n) - C(2*n,n-1) + mod) % mod;

路径计数问题

1. 从 \((0,0)\) 到 \((m,n)\) 的非降路径数等于 \(m\) 个 \(x\) 和 \(n\) 个 \(y\) 的排列数，即\(C_{n+m}^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\) 的非降路径数。所有的的非降路径有 \(C_{2n-2}^{n-1}\) 条。对于这里面任意一条接触了 \(y=x\) 的路径，可以把它最后离开这条线的点到 \((1,0)\) 之间的部分关于 \(y=x\) 对称变换，就得到从 \((0,1)\) 到 \((n,n-1)\) 的一条非降路径。反之也成立。从而 \(y=x\) 下方的非降路径数是 \(C_{2n-2}^{n-1}-C_{2n-2}^{n}\) 。根据对称性可知所求答案为 \(2(C_{2n-2}^{n-1}-C_{2n-2}^{n})=\dfrac{2C_{2n-2}^{n-1}}{n}\)。

3. 从 \((0,0)\) 到 \((n,n)\) 的除端点外不穿过直线 \(y=x\) 的非降路径数：用类似的方法可以得到：\(\frac{2C_{2n}^n}{n+1}\)

经典问题

前缀和非负的+1/-1数列个数

已知 \(n\) 个 \(+1\) 和 \(n\) 个 \(-1\) 构成数列 \(a_1,a_2,…,a_{2n}\), 且前缀和满足 \(a_1+a_2+…+a_k\ge0(k=1,2,…,2n)\)，则满足条件的数列个数 \(f(n)\) 为？

解:

当数列不满足条件时，一定存在 \(-1\) 的个数比 \(+1\) 的个数恰好多 \(1\) 的点, 将这个点后面的 \(+1\) 和 \(-1\), 符号取反, 则变成了一个有 \(n+1\) 个 \(-1\) 和 \(n-1\) 个 \(+1\) 的数列, 可以知道这是一一对应的, 所以不满足条件的数列有 \(C_{2n}^{n+1}\) 个，所以满足条件的数列有 \(C_{2n}^n-C_{2n}^{n+1}=\dfrac{C_{2n}^n}{n+1}\)个

不同构真二叉树的个数

由 \(n\) 个内部节点组成的不同构真二叉树的种数 \(f(n)\) 为？

真二叉树的所有节点的孩子数要么为 \(0\)，要么为 \(2\).

可以转化为先序遍历二叉树, 访问到左儿子 \(+1\), 访问到右儿子 \(-1\), 可以转为 前缀和非负的+1/-1数列个数