作者：余不悔，高二，2018 年 CMO 铜牌获得者。
对于两个有限集合 $A$ 和 $B$，如果存在一个一一映射：$f:A \rightarrow B $，那么就有 $|A|=|B|$。
在某些情况下，如果 $A$ 的元素个数不好求，那么我们可以寻找一个集合 $B$，并建立起 $A$ 到 $B$ 的一个一一映射，然后去计算集合 $B$ 的元素个数，从而将问题解决。在这个过程中，寻找到容易计算元素个数的集合 $B$ 是至关重要的一步。
譬如下面这个大家都很熟悉的例子：
在 $6 \times 6$ 的方格表中，从左下角的 $A$ 点到右上角的 $B$ 点沿方格表的最短路径有多少条？
容易发现，从 $A$ 点到 $B$ 点的最短路径中，全部由 “向上” 和 “向右” 的线段组成，且各有六条。因此，我们建立起集合 $B$，定义它包含 “在 12 条线段中，选择 6 条作为向上线段的方法”。这样，对每一个确定的 $B$ 的元素，都可以唯一对应一种 $A$ 的方法，而对于 $A$ 的每一种方法都可以唯一的生成一个 $B$ 的元素，也就是我们建立了 $A$ 与 $B$ 之间的一一映射。因此，我们知道 $|A|=|B|= \binom{12}{6}$，问题得以解决。
事实上，在我们平时做题经常采用的 “隔板法”，“捆绑法” 都可以视为采取了某种映射方法，不过映射方法远远更为广泛，也更为灵活，这在我们后面的例题中也有体现。
例题
例题 1
- 只由 $1,2,3$ 组成的不大于 $1$ 亿的正整数中，能够被 $3$ 整除的有几个？
-
在集合 $\{ 1,2,3,4,5,6,7,8,9,10\}$ 中，使得元素和为奇数的子集有几个？
解答
对于第一题，所求正整数等价于：只由 $1,2,3$ 组成的，能被 $3$ 整除的八位正整数个数。我们令所有这样的正整数组成集合 $A$，它的个数不方便直接计算，我们转而寻求一个方便计算的集合 $B$。我们考虑，所求正整数是由一个七位正整数末尾添加一个数字得来。那么对于一个只由 $1,2,3$ 组成的七位正整数，要得到能被 $3$ 整除的八位正整数，末尾添加数字的方法有且只有 $1$ 种；而对于集合 $A$ 中的每一个元素，去掉最后一位产生的七位正整数也一定互不相等。也就是说，定义集合 $B$ 包含 “所有只由 $ 1,2,3 $ 组成的 $ 7 $ 位正整数”，集合 $A$ 到集合 $B$ 存在着一一映射关系。所以，答案就是 $7^3$。
对于第二题，我们将原集合看作 $\{ 1\} \bigcup \{ 2,3,4,5,6,7,8,9,10\}$。对于右边这个集合的所有子集，当它元素和为奇数时，属于题目要求的集合 $A$；当它的元素和为偶数时，再加上 $1$ 也属于题目要求的集合 $A$。于是，定义集合 $B$ 表示集合 $\{ 2,3,4,5,6,7,8,9,10\}$ 的所有子集，它与集合 $A$ 存在着一一映射关系。所以，答案就是 $2^9$。
例题 2
将全班 $30$ 名男学生和 $10$ 名女学生排成一列，使得任意两名女同学不相邻，一共有多少种排法？如果是 $m$ 名男同学，$n$ 名女同学呢？
解答
我们先不考虑同性别同学个体之间的差异来计算答案。对于从左到右第 $i$ 个女同学，令 $x_i$ 为她左边的男同学个数。显然，一个排列方法合法当且仅当 $x$ 严格单调上升。而一组确定的 $x$ 也唯一确定了一个排列。也就是说，我们建立了从一个合法排列到一个严格单调上升排列的一一映射。后者的方案数，可以进一步被简化为：从 $\{ 0,1,2,\cdots,30 \}$ 中选择 $10$ 个数字组成 $x$ 序列。所以，答案是 $\binom{m+1}{n}n!m!$。
练习
- 将 $40$ 个小球（小球之间没有区别），放入 $A,B,C,D$ 四个盒子里，其中每个盒子里至少有两个小球，有多少种方法？
-
不定方程 $x_1+x_2+x_3+ \cdots + x_m = n$ 的非负整数解有多少组？
-
从集合 $\{ 1,2,\cdots,n\}$ 中任取 $k$ 个可以重复的数有多少种方案？
例题 3
- 一条直线上分布着 $n$ 个点，这 $n$ 个点之间能组成 $\binom{n}{2}$ 条线段。
- $n \times m$ 的方格表中，以整点为顶点的矩形有 $\binom{n+1}{2}\times\binom{m+1}{2}$ 个。
练习
平面直角坐标系中，$x$ 轴正半轴分布着 $n$ 个点，$y$ 轴正半轴分布着 $m$ 个点。现将每个 $x$ 轴上的点与 $y$ 轴上的点相连，如果其中没有三条线段经过同一个点，求最终形成的交点个数。
例题 4
小明有 $n$ 枚相同的糖果。他每天可以吃若干糖果，但不可以不吃，则小明有多少种把糖果吃完的方法？
解答
我们先考虑使用传统的分类讨论 + 隔板的方法解决这道题。假设小明一共使用了 $i$ 天吃完了这些糖果，此时的方案数为 $\binom{n-1}{i}$，则答案为 $\sum_i^{n-1}\binom{n-1}{i}$。
分类讨论还是一件很麻烦的事情。我们尝试抛开天数这个条件，将问题具体到每颗糖果上。小明吃完一颗糖果后，只有两种选择：马上吃下一颗，或者是明天再吃下一颗。可就是，除了最后一颗糖果，小明要面临这种选择 $n-1$ 次，而这 $n-1$ 次选择唯一对应了一种把糖果吃完的方案。也就是说，$n-1$ 次选择构成的序列与吃糖果方案存在一一映射关系。于是，答案就是 $2^{n-1}$。
显然，$\sum_i^{n-1}\binom{n-1}{i} = 2^{n-1}$。
练习
集合 ${ 1,2,3,\cdots,n}$ 一共具有多少交集为空集的子集对？
有时我们在实行上述的映射方法时可能会遇到一些困难，所想要的集合 $B$ 并不容易寻求，我们可以退而求其次，寻找一些变通的方法。
如果我们能在两个有限集 $A$ 和 $B$ 中完成这样的 “配对”：使得 $A$ 中每个元素可以与 $B$ 中 $k$ 个元素配对，而 $B$ 中的这 $k$ 个元素又可以唯一地与 $A$ 中那个元素配对，那么我们就可以知道 $|B|=k|A|$，这时再对 $B$ 去求元素个数就可以了。
这样的变通还有意想不到的好处：我们的配对关系有可能不是局限在直接构造出我们所需要的 $B$，而是可能在于从 $n$ 的情况，配对到之前的情况。这就启发我们可以通过递推方法来计数，即借助递推关系，求解数列，得到最终答案。
例题
例题 1
将 $n$ 个不同的实数排在圆周上一共有多少种排法？
解答
如果将这个园拆成一条链，显然有 $n!$ 中排列方式。我们发现，将这些排列放到一个圆上，产生了若干种本质相同的排列方法。就拿数列 $(1,2,3,4)$ 来说明，在圆周上和它本质相同的数列还有 $(2,3,4,1)$ ，$(3,4,1,2)$ 以及 $(4,1,2,3)$ 。我们可以发现，对于 $n$ 个数的一个排列，存在着另外 $n-1$ 个排列与它在圆周上本质相同（即可以通过旋转得到）。那么 $n$ 的所有排列中，将每 $n$ 个本质相同的排列视为一组，我们就构建了从这 $n$ 个排列方式到圆上的一种合法排列方案的映射。所以，本题答案为 $\dfrac{n!}{n}=(n-1)!$。
例题 2
有一个 $6 \times 6$ 的方格表，有一小人 $a$ 从 $A(0,0)$ 走到 $B(6,6)$，有一小人 $b$ 从 $C(3,0)$ 走到 $D(6,3)$，它们各自走的都是最短路径，小人 $a$ 的路径称为 $f$，小人 $b$ 的路径称为 $g$。问：有多少个路径对 $(f,g)$ 使得 $f$ 和 $g$ 没有公共点？
解答
我们先考虑 $(f,g)$ 有公共点的情况，先假设出现的第一个公共点为 $E(4,2)$。
如图，红色的路径为 $f$，而黄色的为 $g$。现在我们让两个小人完成他们的路程，下图是其中的一种情况。
如何刻画这种包含公共点的路径对 $(f,g)$ 呢？这里有一个技巧，把 $E$ 之后的路径互换。互换之后的情况如下。
也就是说，小人 $a$ 从点 $A$ 跑到了点 $D$，小人 $b$ 从点 $C$ 跑到了点 $B$。请仔细地思考，互换的目的是什么？首先我们明确，能进行这样的互换，当且仅当 $(f,g)$ 包含公共点。而互换之后的路径，相当于 $A \rightarrow D , C \rightarrow B$ 的路径对。
进一步发现，不合法的路径对 $(f,g)$ 与一种互换路径方式形成一一映射关系，而互换后的路径与 $A \rightarrow D , C \rightarrow B$ 的路径对形成了一一映射关系。也就是说，$A \rightarrow D , C \rightarrow B$ 的路径对个数就是不合法路径对 $(f,g)$ 的个数！
在这篇文章的开头就已经讲解了最短路径数量的算法，在此不再赘述。本题答案为 $\binom{12}{6}\times\binom{6}{3}-\binom{9}{3}\times\binom{9}{6}$。
例题 3
有一条道路上有 7 个停车位，有 7 名司机 $A_1,A_2,\cdots,A_7$ 在此停车。司机 $A_i$ 偏爱位置 $a_i$，所以他会先将车开到 $a_i$ 号车位，如果那里已经有车了，他就会向后开到下一个空位；如果后面已经没有空位，他就会扬长而去。问：有多少组 $(a_1,a_2,\cdots,a_7)$ 使得每一位司机都能停进车位？
解答
本题直接计数似乎不是很可做。我们要尝试建立的是从一个确定的序列 $a$ 到一个合法的，没有空车位的最终状态的映射，同时，一些可能的序列 $a$ 使停车过程无法继续进行，很难直接计算这样的情况。
我们思考，如果停车位首尾相接会是怎样的情况？显然，当你直接把 1 号位和 7 号位相连时，所有可能的序列 $a$ 都能填满车位，你就凉凉了。
有一个巧妙的方法是，在 7 号位后添加一个 8 号位，然后将 8 号 与 1 号相连。此时，我们定义新的序列 $a’$，使得 $a’_i\in[1,8]$。对于一个确定的序列 $a’$，它会在停车位上留下一个确定的空位。由于车位首位相接，$(a’_i+k) \mod 8+1, k \in [0,7]$ 这 8 个序列本质相同，空下来的车位根据 $k$ 值的不同位于不同的位置，其中必有一个 $k$ 使得空位恰好为 8 号位。也就是说，每 8 个本质相同的序列 $a’$ 中，有一个填满了 1 号到 7 号位。
仔细思考这是为什么。首先，合法的序列 $a$ 中不可能出现数字 8，而上述合法序列 $a’$ 中也不可能出现数字 8，否则 8 号位一定不可能是空位；其次，使 8 号位为空位的序列 $a’$ 带来的确定的停车过程中，不可能有车辆经过 8 号位来到 1 号位，否则 8 号位一定不可能是空的。
所以，令环上本质相同的序列 $a’$ 为 1 组，每组有 8 个不同的序列，其中必有一个序列使得 8 号位空置；而 8 号位空置等价于对应的序列 $a’$ 合法。所以，答案为 $\dfrac{8^7}{8}=8^6$。
练习
有一个花坛，其由一个中心圆盘和 $n$ 段有序圆环组成（下图所示为 $n=4$ 的情况），现有 4 种颜色，要给花坛的每一区域染色，使得相邻区域的颜色互不相同，问一共由多少种不同的染色方案。
