高中数学奥赛讲义：映射与计数在解竞赛题中的应用.doc

高中数学奥赛讲义：映射与计数在解竞赛题中的应用【内容综述】利用映射来解决计数问题，就是通过建立集合A与另一集合B之间的映射，把对集合A的计数转移到对集合B的计数。实现这种转移的关键是：（1）选择适当的便于计数的集合；（2）建立集合间的映射关系。设f：是集合A到集合B上的映射，那么（1）若f为单射，则。（2）若f 为满射，则。（3）若f为一一映射，则。【例题分析】 例1 从的棋盘中，取出一个由三个小方格组成的L形，有多少种不同取法？这里棋盘是指m条横线与n条竖线所构成的棋盘。解 每种取法，都有一个点与它对应，这个点就是所取L形中三个小方格的公共点（如图1），它是棋盘上横线与竖线的交点，且不在棋盘的边界上。从图2可看出，每个点对应于4种不同取法，这4种取法构成一个“田”字形。而每个“田”字形都有唯一的中心。（例如点B），即映射f：“田”字形“田”字形中心，是棋盘上由小方格组成的“田”字集合到棋盘内横线与竖线的交点集（不包括边界上的点）的一一映射。显然棋盘内横线与竖线的交点有个，所以，共有种不同取法。例2 求n元集合A的所有子集的个数解 设集合A的所有子集的集合为P（A），B为集合A到集合的全体映射的集合，对于任意的，可唯一确定一个从集合A到集合的映射（通常称为集合M的特征函数），即有唯一的与M对应。反过来，对于任意的，有唯一的集合。显然，且就是。因此，映射f：是集合P（A）到B的一一映射。由于n元素集A到集合的映射的个数为，即，根据对应原理说明 一般地，集合到集合的所有映射的个数为。例3 中日围棋擂台赛，双方各派6名队员按预定顺序出场，直到最后一方取胜，问可能出现的比赛过程种数有多少种？解 设中国队员对应红球，日方队员对应白球。将被淘汰队员对应的球按被淘汰的时间顺序一一排列出来。负方队员全部被淘汰，则相应球全部排出，然后将胜方所剩队员对应的球依次排在后面。由于双方队员出场顺序已定，故可设同色球之间无区别，于是一种比赛过程就对应于6个红球和6个白球的一种排列；反之，6个红球和6个白球的一种排列对应着一种比赛过程，即球的不同排列与不同比赛过程之间存在一一对应关系。6个红球和6个白球的不同排列数为，此即所求比赛过程种数。说明 在某种映射下，两个集合元素间一一对应，该映射即为一一映射，所以对于明显的一一映射只须指出两集合间的一一对应关系，就可运用对应原理。例4 求m元方程的正整数解的组数。解法一 由于数组中各数可以重复，且大小无序，因此作如下映射：显然 且一一对应，所以，映射是一一映射。因为，满足的数组有个，所以所求方程解的组数为。 解法二 考虑长度为n的线段AB。方程的任一组解对应于把线段分成m节的一种分法，其中第一节的长度为，第二节的长度为，第m节的长度为，而每一种分法又对应于线段长n-1个分点中取出m-1个分点的一种取法。反过来，线段n-1个分点中取出m-1个分点的任一种取法，都把线段AB分成m节。令依次取m节的长度，就得到方程的一组解。所以，原方程解的组数就是线段AB上n-1个分点中取出m-1个的不同取法的种数。说明 若把问题改为：求m元方程的非负整数解的组数，只要令，则化为求方程的正整数解的组数，由例4可知所求解的组数为。例5 设为A的三元子集，若满足为A的“好子集”，求A的“好子集”的个数。解 令作映射。f是到上的一一映射。事实上，当时，那么即。另一方面，若，则，即。于是由对应原理，即A的“好子集”有个。例6 设n为正整数，若的一个排列中存在，使成立，则称该排列具有性质P。证明：具有性质P的排列比不具有性质P的排列多。证明 设A是由不具有性质P的排列构成的集合，B是恰有一对满足的排列构成的集合，C是具有性质P的所有排列构成的集合，显然，从而。设，其中必有一个，使，于是调整的位置如下，该排列仅有一对相邻数满足，从而。上述调整构成了一个A到B的映射，因此，。又，故，即具有性质P的排列比不具有性质P的排列多。例7 已知，并且求的个数。解 由知中有n个+1，n个-1，这样的有序数组有个。下面考虑这样的有序数组中有多少不符合，设其个数为。如果不符合，那么一定存在最小的自然数，满足（1）；（2）将统统改变符号，这一对应改为n+1个+1，n-1个-1组成的有序数组。反之，对于任何一个n+1个+1，n-1个-1组成的有序数组，由于+1多于-1，必然存在一个最小的自然数s，满足。将变为，就得到一个n个+1，n个-1组成的不符合的有序数组，所以，f是一一映射，由对应原理知等于n+1个+1，n-1个-1组成的有序数组的个数，即。因此，符合题目条件的有序数组的个数为例8 已知数列满足。对每一个整数，求满足条件的下标n的个数。解 将满足的自然数n用二进制表示为，这里，可以证明事实上，如果为偶数，则，均有为偶数，且；如果为奇数，则，均有为奇数，且所以式成立。反复利用式可知上式右边为k个+1或-1的和。所以，当k为奇数时，的右边为奇数，不会等于0，这表明，当k为奇数时，满足条件的下标n的个数为0。当k为偶数时，若，则式右边恰有个+1，个-1。设，n的二进制表示为，式确定了一个A到B的映射：。由于A中任意两个元素的二进制表示首位都为1，设。并设j为使的最大下标。则。这说明是A到B的单射。又易知，所以又是A到B的满射，从而是A到B的一一映射。故满足，且的下标n的个数为B中恰有个-1的有序数组的个数，即。