构造映射
我要成为组合糕手
当计算有限集合$M$中的元素数量比较困难时，我们设法建立$M$到另一个集合$N$之间的映射。若N中的元素$|N|$比较容易算出，且$M$到$N$构成双射，则有$|M| = |N|$，这样就可以通过计算$N$而求出$M$。也有些时候，我们利用构造单射或满射来得到不等关系。
在此之前，我们先做 一些说明，我们用 ${n \choose m}$ 表示 $C^{m}_{n}$, 也就是从$n$个物品中选出$m$个物品的方案数，其等价于下面不等式的解的数量：
$$
0 \lt a_1 \lt a_2 \lt … < a_m \le n
$$
通常，我们选择出来的$m$个物品，会用一个$m$元组$(a_1,a_2,⋯,a_m)$来表示，其中$a_i$是第$i$个被选物品的编号，每个$a_i$是$1$到$n$之间的整数，用递增的编号表示法，确保每种选择只表示一次、不会重复。
引例
让从一个例子入手：求 $x + y + z = 10$ 的正整数解的数量，也就是把$10$个小球分成$3$堆的方案数, 很显然，答案是${9 \choose 2}$, $10$个小球中间有$9$个缝隙，我们任意找$2$个缝隙作为划分位置，就可以将其分成$3$堆。
现在，我们改变一下问题：求 $x + y + z = 10$ 的非负整数解的数量，这下有$0$了，就不能用隔板法了！有没有一种办法将这个问题转换为正整数解的形式呢？
我们令 $X = x + 1 \gt 0$， $Y = y + 1 \gt 0$， $Z = z + 1 \gt 0$, 所以$X + Y + Z = 13$, $(X, Y, Z) $与 $ (x, y, z) $构成了一个双射，我们每找到一组 $(X , Y, Z) $的解就能找到一个 $(x, y, z) $ 的解！这样问题就变成了求 $x + y + z = 13$ 的正整数解的数量, 答案是${12 \choose 2}$。
注意：我们构造出的映射必须要验证是双射，才能完成问题转换，否则只能得到较弱的不等关系。
不定方程的一般结论
我们将引例进行推广，得到更一般的形式：
定理1：$\sum_{i = 1}^{m}x_i= n$ 的正整数解的数量为 $ n - 1 \choose m - 1$。
定理2：$\sum_{i = 1}^{m}x_i= n$ 的非负整数解的数量为 $ n + m - 1 \choose m - 1$，也等价于 $m$ 个不同元素中取出 $n$ 个可重复的元素的方法数。
下面我们考虑 $\sum_{i = 1}^{m}x_i \le k$ 的非负整数解的数量，一个常规思路是求下面$k + 1$个不定方程的解的数量和(两两独立)：
$$
\sum_{i = 1}^{m}x_i = 0,1,2…k
$$
利用定理2，解的数量为：
$$
\sum_{i = 0} ^ {k} {m - 1 + i \choose m - 1}
$$
根据朱世杰恒等式 $\sum_{i = a} ^ {k} {i \choose a} = {n + 1 \choose a + 1}$
$$
\sum_{i = 0} ^ {k} {m - 1 + i \choose m - 1} = \sum_{i = m - 1} ^ {k + m - 1} {i \choose m - 1} = {k + m \choose m}
$$
下面我们考虑构造映射的方式求解， $\sum_{i = 1}^{m}x_i \le k$ 的非负整数解的数量 等价于 $w + \sum_{i}^{m + 1}x_i = k$ 的非负整数解的数量，对于原来的解空间$(x_1…x_m)$ 和新的解空间 $(w, x_1… x_m)$构成了一个双射，利用定理二，我们可以得到答案 ${k + m \choose m}$。
定理3： $\sum_{i = 1}^{m}x_i \le k$ 的非负整数解的数量为 ${k + m \choose m}$。
不等式组的映射
有的时候，我们得到的条件是一个不等式组，不等式之间有着不同的约束关系，不过处理技巧基本类似，都是要从未知的问题中找到与已知的联系，从而转换为已知来进行计算。
例题1
考虑把$n$个人排成一队，现从中挑选出$k$个人，要求这$k$个人没有在原来队列中相邻的人，共有多少种挑法？
我们将挑出来的人记为$a_1…a_k$, 于是
$$
\begin{align*}
0 \lt a_1 \lt a_2 \lt … < a_k \le n \\
a_{i+1} - a_{i} >= 2
\end{align*}
$$
令
$$
b_i = a_i - i + 1
$$
则
$$
0 \lt b_1 \lt b_2 \lt … \lt b_k \le n - k + 1
$$
因此答案为 ${n - k + 1 \choose k}$。用上面的方法也很容易将 $a_{i+1} - a_{i} >= 2$ 推广到 $a_{i+1} - a_{i} >= m$ 的情况。
例题2
在一个长度为$n$的数轴上，选出$k$ 条长度大于$1$的线段， 要求线段除边界点上都不能重叠，求方案数。具体可以参考原题。
我们定义这个k个线段的开始和结束分别为$a_i$和$b_i$，$i = 1…k$，于是：
$$
0 \lt a_1 \lt b_1 \le a_2 \lt b_2 \le a_3 … < b_k \le n
$$
令
$$
\begin{align*}
A_i &= a_i + i - 1\\
B_i &= b_i + i - 1
\end{align*}
$$
则
$$
0 \lt A_1 \lt B_1 \lt A_2 \lt B_2 \lt A_3 … < B_k \le n + k - 1
$$
因此答案为 ${n + k - 1 \choose 2k}$。
卡特兰数
卡特兰数(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_0$ | $H_1$ | $H_2$ | $H_3$ | $H_4$ | $H_5$ | $H_6$ | … |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 5 | 14 | 42 | 132 | … |
封闭形式求解
由于这个7个问题等价， 我们借助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)$，有多少个满足条件的数列？
我们从问题的反面入手，寻找所有的非法序列，将总方案减去非法方案得到合法方案，我们考虑第一个$k_0$ 满足， $a_1+a_2+ \cdots +a_{k_0} \lt 0$，注意到$k_0$一定在奇数位置， 记到$k_0$位置时有$m+1$个$-1$，$m$个$1$， 即 $k_0 = 2m + 1$。
此时，还剩下$ n - m $个 $+1$，$ n - m - 1$个$ - 1$， 我们将剩下的$+1$、$-1$进行对调，因此还剩下 $n - m $个$ -1$，$ n - m - 1$个 $+1$， 对调后的序列由$ n + 1 $个$ -1$， 和$ n - 1$ 个$+1 $组成的序列。
下面证明新构造$S_2$的序列和原来的非法序列$S_1$形成了一个双射：
1、$S_1 \rightarrow S_2$ 是显然的，因为$S_1$按照上述操作一定可以唯一构造出$S_2$。
2、由于$S_2$中 $-1$的数量比$+1$ 的数量多两个，所以一定有第一个$k_1$ 满足， $a_1+a_2+ \cdots +a_{k_1} \lt 0$， 我们将$k_1$之后$+1$、$-1$进行对调，这样就唯一对应了一个$S_1$，于是我们证明了 $ S_2 \rightarrow S_1 $。
根据1、2， 我们有$S_1 \leftrightarrow S_2$， 对于$|S_2| = {2n \choose n - 1} = |S_1|$， 因此合法方案为${2n \choose n} - {2n \choose n - 1}$，化简得
$$
\begin{align*}
{2n \choose n} - {2n \choose n - 1}
&= {2n \choose n} - \frac{(2n)!}{(n + 1)!(n - 1)!} \\
&= {2n \choose n} - \frac{(2n)!n}{(n + 1)!(n - 1)!n} \\
&= {2n \choose n} - \frac{(2n)!n}{n!n!(n + 1)} \\
&= {2n \choose n} - \frac{(2n)!}{n!n!}\frac{n}{n + 1} \\
&= {2n \choose n} - {2n \choose n}\frac{n}{n + 1} \\
&= \frac{1}{n + 1}{2n \choose n}
\end{align*}
$$
定理4： 卡特兰数的通项公式为$H_n = \frac{1}{n + 1}{2n \choose n}$。
由于第一个位置一定是$+1$, 我们考虑与第一个位置匹配的$-1$的位置，因此我们也可以得到如下递推公式：
定理5： 卡特兰数的递推公式为$H_n = \sum_{i = 0} ^ {n - 1} H_i*H_{n - i}$。
总结
定理1：$\sum_{i = 1}^{m}x_i= n$ 的正整数解的数量为 $ n - 1 \choose m - 1$。
定理2：$\sum_{i = 1}^{m}x_i= n$ 的非负整数解的数量为 $ n + m - 1 \choose m - 1$，也等价于 $m$ 个不同元素中取出 $n$ 个可重复的元素的方法数。
定理3： $\sum_{i = 1}^{m}x_i \le k$ 的非负整数解的数量为 ${k + m \choose m}$。
定理4： 卡特兰数的通项公式为$H_n = \frac{1}{n + 1}{2n \choose n}$。
定理5： 卡特兰数的递推公式为$H_n = \sum_{i = 0} ^ {n - 1} H_i*H_{n - i}$。