是一些关于折线法和 Catalan 数的基本组合技巧。

# 折线法

最基本的折线法是无限制的情况。问题的具体描述如下：

在一个平面直角坐标系 $xOy$ 中，我们取起点 $A(x_1,y_1)$ 及终点 $B(x_2,y_2)$, 其中 $x_i,y_i \in \mathbb{Z}$. 假设一个质点从起点 $A$ 出发，每步操作可以选择向右上走一步 (即横纵坐标值同时 $+1$ ) 或向右下走一步 (即横坐标 $+1$, 纵坐标 $-1$), 问存在多少种不同的走法？

首先，我们需要考虑能否到达终点。这要求横纵坐标差的奇偶性相同，即 $x_2-x_1 \equiv y_2-y_1 (\mathrm{mod}\,2)$. 此外，还要求 $x_2-x_1 \geq y_2-y_1 \geq 0$, 否则即便一直向上走也达不到。

在这种情况下，显然在总共 $x_2-x_1$ 步中，有 $(x_2+y_2-x_1-y_1)/2$ 步向右上，$(x_2-y_2-x_1+y_1)/2$ 步向右下。于是总的取法为 $\binom{x_2-x_1}{(x_2+y_2-x_1-y_1)/2}$. 我们令 $x = x_2-x_1$，$y=y_2-y_1$, 则结果简化为 $\binom{x}{(x+y)/2}$.

这样的折线法并没有什么意义，因为其就是组合数 $\binom{n}{m}$ 的再叙述。但如果将折线法的问题强化为下面的形式，那么折线法在组合计数中将具有相当的意义。

题目背景同上，如果起点 $A(x_1,y_1)$, 终点 $B(x_2,y_2)$ 同在 $x$ 轴上方，那么质点移动路径中，与 $x$ 轴有公共点的路径有多少？

这时，我们考虑一个反射。作 $A'(x_1,-y_1)$. 显然，若存在 $A\to B$ 的路径，则必然存在 $A' \to B$ 的路径。根据连通性，$A' \to B$ 必然与 $x$ 轴相交，我们设其中横坐标最小的交点为 $(x_0,0)$. 那么我们将路径 $A'\to B$ 中位于 $x=x_0$ 左侧的部分沿 $x$ 轴进行轴对称，便得到了 $A \to B$ 的且与 $x$ 轴相交的路径。容易验证，这种映射是双射。我们称此结论为反射原理。

根据反射原理，可以得到与 $x$ 轴有公共点的路径总数为 $\binom{x_2-x_1}{(x_2-x_1+y_2+y_1)/2}$.

在此基础上，我们可以计算出 $A \to B$ 中与 $x$ 轴不相交的路径数目。为 $\binom{x_2-x_1}{(x_2-x_1+y_2-y_1)/2} - \binom{x_2-x_1}{(x_2-x_1+y_2+y_1)/2}$.

于是，便引出了第三个问题：

题目背景同上，$A,B$ 同在 $x$ 轴上方，问从 $A$ 到 $B$ 的路径中，不穿过 $x$ 轴的路径总数有多少？

注意到，不穿过 $x$ 轴等价于与轴 $y=-1$ 不相交，于是将路径整体上移一个单位，就转化成不与 $x$ 轴相交的问题。

构造点 $A'(x_1,y_1+1)$, $B'(x_2,y_2+1)$，则从 $A'$ 到 $B'$ 不与 $x$ 轴相交的路径数为 $\binom{x_2-x_1}{(x_2-x_1+y_2-y_1)/2} - \binom{x_2-x_1}{(x_2-x_1+y_2+y_1+2)/2}$.

这个问题就具有一定的意义了。我们将折线的路径作对应，可以解决许多相关的计数问题。例如我们可以构造以下的问题：

甲乙两人参加竞选，甲获得 $m$ 张选票，乙获得 $n$ 张选票，且 $m>n$, 那么在逐一唱票的过程中，甲的票数一直领先乙的点票记录有多少种可能？

这属于与 $x$ 轴恒不相交的问题，起点和终点依次为 $(1,1)$ 和 $(m+n,m-n)$ (因为第一票必定为甲获得)。于是代入公式，其总可能数为 $\binom{m+n-1}{m-1}-\binom{m+n-1}{m} = \frac{m-n}{m+n}\binom{m+n}{m}$.

这是一个经典的问题，我们称之为选择问题。

收银员向 $2n$ 人各收费 $50$ 元。$2n$ 人中，有 $n$ 人带了 $1$ 张 $100$ 元的钞票，另外 $n$ 人带了一张 $50$ 元的钞票。若收银员最开始没有零钱，问这 $2n$ 人有多少种排队方法，使得收银员能够完成收银而不需要借钱找零？

这可以转化成 $(0,0)$ 到 $(2n,0)$ 的，不穿过 $x$ 轴的总路径问题。于是其结果为 $\binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}$.

而 $\frac{1}{n+1}\binom{2n}{n}$ 就是著名的 Catalan 数。

# Catalan 数

Catalan 数具有相当广泛的组合意义。我们在此选择递推法定义 Catalan 数。我们定义 $C_n$ 为第 $n$ 个 Catalan 数，满足 $C_0=1$ 且 $C_{n+1} = \sum_{k=0}^nC_kC_{n-k},\,n \in \mathbb{N}_+$. 下面我们求解 $C_n$.

采用生成函数法，构造形式幂级数 $C(x)=\sum_{k=0}^\infty C_kx^k$.

中间使用广义幂级数。