第七十二讲 映射 讲义-2026年高中数学竞赛

第七十二讲 映 射 1. 映射的结构 研究一个集合 ,有时候直接研究颇为不易,可以通过研究某些映射 或者 ,间接地获得关于 的信息,这在数学中是重要的思想。 设 是 到 的映射,记 称为 的像集。若 ,则称 是满射。若对任意 ,均有 ,则称 是单射。若 既是单射又是满射,则称 是双射或一一对应。 对子集 ,记 称为 的 -原像,当 时, 简写为 ,称为 的原像。 在计数问题中,特别重要的是 均为有限集的情况。此时有显然的等式, 进而对于满射 ,有 ; 对于单射 ,有 ; 对于双射 ,有 。构造一一对应来证明两种计数对象个数相等,在组合计数中称为双射论证,是非常重要的方法。若对任意 ，均有 ，则称 是 对 1 映射，此时 。 一个集合 到自身的双射 ,称为 上的变换。对任意 ,称下述集合 为 所在的轨道,这里对 表示 个 的复合, 表示 个 的复合。容易验证,任意两个轨道要么完全相同,要么不相交。因此所有不同的轨道给出了 的划分。 设 是有限集, 是 上的变换,则每个轨道必定是有限集,此时也称为循环圈, 因为一个轨道 对于 的映射有循环的结构, 此时也用 来表示这个循环圈,注意将 做循环排列后是同一个循环圈,因此一个循环圈可以看作 的圆周排列。 设 是 到自身的双射,则对应了一个排列 , 也称为一个置换。对于 ，若 ，则称 是 的一个逆序对。 的逆序对的个数称为 的逆序数,记为 。若 仅交换两个数 ,即 , ,对 ,则称 是一个对换,记为 。如果将排列 , 中交换 ,得到新的排列记为 ,则 。 不难证明, 复合一个对换后,逆序数的奇偶性改变。由于任何排列总可以由恒等排列通过对换得到,即任意置换 总可以写成对换的复合(写法并不唯一), 可知 。将 的奇偶性称为置换 的奇偶性,因此 表示为对换的复合,对换个数的奇偶性也是确定的,就是 的奇偶性。 例 1 是否存在映射 ,满足对任意整数 ,有 ? 解 不存在。假设存在满足条件的映射 ,由于 是 到自身的双射，易知 也是 上的变换。考虑一个轨道 由条件知, ,是模 2021 的一个同余类。同样地, ,也是模2021一个同余类。且这两个同余类不同,否则存在 ,使得 ,导致 ,从而轨道 是有限集, 这不可能。因此每个轨道恰是模 2021 的两个同余类的并集, 但是所有轨道构成了整数集的划分, 2021 是奇数, 这不可能。 例 2 给定正整数 ,设 。函数 满足对任意 都有 求这样的函数 的个数。 解 用 表示 的 次迭代。对于 ,若 ,则 故 ,这表明 是单的,又 是有限集合,故 也是满的,从而 是 到自身的双射, 可分解为不相交循环圈。由条件知, 故每个循环圈的长度为 8 的约数,即只能是 1,2,4 或 8 。对于长度为 1,2,4 的循环圈上的每个数 ,由于 只能是 。所以不存在长度为 2,4 的循环圈,长度为 1 的循环圈也至多一个。 故当 时,不存在这样的函数。当 时,没有长度为 1 的圈,有 个长度为 8 的圈,且对径点两数之和等于 。 将 个数分成 对, ,每个循环圈上恰为 4 对。将这 对数分成 组,每组 4 对,不计 组之间的次序,有 种方式。将一组中的 4 对数排成一个循环圈,使得每一对数是对径点的方法数有 种(先固定一对数，另三对数的排列有 3 种，排定另三对数的顺序后，每一对数可以在对径点上交换,又有 种),因此满足要求的 共有 当 时,恰有一个不动点, 。其余 个数按照和等于 1 配对,分为 对,排列成 个长度为 8 的循环圈,方法数也是 。 综上所述，当 时，满足题意的 不存在; 当 时，满足题意的 个数为 。 2. 应用举例 例 3 设 是正整数,称集合 的一个排列 具有性质 ,若存在 ,使得 。证明: 对任何 ,具有性质 的排列比不具有性质 的排列多。 证明 称 与 是一对伙伴, ,具有性质 的排列即至少有一对伙伴是相邻两项的排列。 任取一个不具有性质 的排列 ,则存在唯一的 ,使得 ,将这个排列对应于 ,即将 移到 之前，所得排列具有性质 ，且恰有一对伙伴是相邻两项，并且不是前两项。 这样的对应显然是单的。另一方面，存在具有性质 的排列，前两项即为一对伙伴， 故具有性质 的排列多于不具有性质 的排列。 评注 在 例 5 中,我们利用容斥原理和 Bonferroni 不等式给出了一个证明, 这里采用构造映射的方法给出了另一种证明。 例 4 设 是奇素数。考虑集合 的所有 元子集,求其中元素和被 整除的 元子集的个数。 解 记 ,其中 。用 表示集合 的所有 元子集的集合, 为 的所有子集的集合。称元素和被 整除的 的子集为好子集。 定义 如下,对 ,设 ,则令 即在模 意义下将 中每个元素加 1 。从而 ,对 是将 映到自身的双射,每个 所在轨道大小均为 。 定义 如下,对 ,设 ,则令 。由 的轨道可知 所在 轨道大小均为 1 。除 外, 每个 轨道大小均为 ,且每个 轨道中 个集合的元素和恰是模 的完系,因此恰有一个是好子集。故好子集个数为 2. 评注 在 例 7 中,我们用生成函数以及多项式的方法得到了相同的结论。 这里采用映射的方法构造 上的轨道分解。 例 5 正整数 的一个划分 ,是指将 写成一个或多个正整数之和,且按非减顺序。对任一划分 ,定义 为划分 中数 1 出现的个数, 为 中出现的不同数的个数。 证明: 对任意正整数 ,其所有划分 的 之和等于 之和。 证明 设 为 的所有划分的个数,并规定 。我们证明 对 的一个划分 ,设有 个 1,在 中删去 个 ,得到 的划分。将 对应于这 个划分,当 取遍所有 的划分时, 的所有划分恰好被对应一次,因此有左边的等式成立。 对 的一个划分 ,设有 个不同的数 ,从 中删去 ,得到 的划分,将 对应于这 个划分。当 取遍所有 的划分时, 的所有划分也恰好被对应一次,因此有右边的等式成立。 例 6 正整数 的一个无序分拆是指将 写为若干个不计次序的正整数之和的表示,记 为 的所有无序分拆构成的集合。对于一个分拆 ,记 为 中恰出现一次的数的个数, 是 中数 的出现次数。证明: 对任意正整数 ,有 证明 记左边和数为 ,右边和数为 。我们归纳证明 时,直接计算可知 。 假设 ,且结论在小于 时均成立。对于 的分拆 ,若其中含有 2,则在 中删去一个 2,得到 ,且 。反之,对任意 的分拆, 添上一个 2 后得到 的含 2 分拆。故 。由归纳假设, , 故只需证明 。 对于 的一个分拆 。若 仅出现一次, 称 是好对。若 ,且 仅出现一次,则称 是极好对。 即为 的所有分拆中好对和极好对的个数总和。 (1) n 的所有分拆中的好对与 n-1 的分拆一一对应，从而好对个数等于 。这是因为,若 是好对,则将其对应于 的分拆 ,恰好一一对应于 的所有分拆。 (2) n 的所有分拆中的极好对与 n-2 的分拆中的所有好对和极好对一一对应。 若 是极好对,则对应于 的划分 1) 中的好对或极好对 (注意若 ,则前面的项都忽略, 在 中必然只出现一次)。这也是一一对应。 综合 (1) 与 (2) 可得 ,从而结论获证。 例 7 设整数 ,且 。在集合 上考虑由 所定义的双射 ,这里 表示 模 的最小非负余数。于是 被划分为若干个 -轨道。例如, 时, 被划分为 3 个轨道: , 8,4),(5)。 证明: 时, 的轨道数是奇数。 证明 一个长度为 的轨道,即一个循环圈 可以写成 个对换的复合, 设 的轨道数为 ,轨道的长度分别为 的逆序数为 ,则 因此 的奇偶性即为 的奇偶性。令 是 的所有逆序对的集合,将 划分为 ,其中 对任意 , 因此 。从而若 ,则 ; 反之,若 ,则 。于是我们有双射 , 。 而 当且仅当 ,且 ,这又等价于 ,故 。 因此 当 时, 又 ,因此 是奇数。 学科网（北京）股份有限公司 $