惊奇地发现自己 OI 没有白学
卡特兰数
(2016·全国卷 Ⅲ) 定义「规范 01 数列」${a_n}$ 如下：${a_n}$ 共有 $2m$ 项，其中 $m$ 项为 $0$，$m$ 项为 $1$， 且 $\forall\ k \leq m$， 有 $a_1,\ a_2,\cdots,\ a_k$ 中 $0$ 的个数不少于 $1$ 的个数，若 $m=4$ ，则不同的「规范 01 数列」共有（ C ）
A. 18 个
B. 16 个
C. 14 个
D. 12 个
老师：「这个题我们也没有好的做法，一个一个枚举就好了」
（你只是不想讲一些奇怪的东西把大家的脑子搞乱吧（x
注意到题中描述的实际上就是配对的括号序列，所以我们可以尝试这样构造合法的括号序列：
一个长度为 $2m$ 的合法序列可以由长度为 $2i$ 和 $2m - 2 - 2i$ 的两个序列拼成，类似…这样：
2m == 6
[][____]
[[]][__]
[[__]][]
[[____]]
所以 dp 方程也就呼之欲出了（其实就是卡特兰数的递推式），
记 $f(m)$ 为长度为 $2m$ 的「规范 01 数列」的数量，那么 $$ f(m)=\sum_{i=0}^nf(i)f(m-i) $$
值得一提的是在请教纸夜姐之前我推出了大约 3~5 个假公式
DAG 路径计数
（2016·全国卷Ⅱ）如图，小明从街道的 $E$ 处出发，先到 $F$ 处与小红会合，再一起到位于 $G$ 处的老年公寓参加志愿者活动，则小明到老年公寓可以选择的最短路径条数为（ B ）
+---------------------------------------G | | | | | | | | | | | | | | | | | | | | | | | | | +-------------------F-------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | +---------------------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | E---------------------------------------+A. 24
B. 18
C. 12
D. 9
我们只需要 xjb 统计一下就行了
+-------------------1---------2---------3
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
1---------3--------6,1--------1---------1
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
1---------2---------3-------------------+
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
1---------1---------1-------------------+
所以答案就是 $6\times3 = 18$
传球游戏
（2018·河北保定质检）三个人踢毽，互相传递，每人每次只能踢一下，由甲开始踢，经过 $4$ 次传递，毽又被踢回给甲，则不同的传递方式有：（ B ）
A. 4 B. 6 C. 10 D. 16
记 $f(n),\ g(n),\ k(n)$ 分别为「经过 $n$ 次传递后，毽子在 甲/乙/丙 的手里」，考虑 $n = 4$ 的情况，由题意，此时毽子在甲的手里。那么，在上一次传递时，毽子一定在乙或丙的手里。换句话说，毽子由乙或丙传递给甲。
那么我们就有： $$ f(n)=g(n-1)+k(n-1) $$ $$ g(n)=f(n-1)+k(n-1) $$ $$ k(n)=f(n-1)+g(n-1) $$
往里面代值计算：
| Function\Value of $n$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $f(n)$ | 1 | 0 | 2 | 2 | 6 |
| $g(n)$ | 0 | 1 | 1 | 3 | 5 |
| $k(n)$ | 0 | 1 | 1 | 3 | 5 |
所以答案就是 $f(4) = 6$ 了