【笔记】映射方法在几何计数中的应用
作者:余不悔,高二,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 种颜色,要给花坛的每一区域染色,使得相邻区域的颜色互不相同,问一共由多少种不同的染色方案。