映射的计数问题(经典)

1、一、一般型映射的计数问题是指课本中介绍的映射知识，这类问题常涉及有求元素个数、集合个数、映射个数等，较简单的可用枚举法、图表法、分类讨论法，适当时要借助于排列组合的知识 例1(2000年全国高考题) 已知映射f：AB，其中，集合A3，21，1，2，3，4，集合B中的元素都是A中元素在映射f下的象，且对任意的aA，在B中和它对应的元素是|a|，则集合B中元素的个数是( )(A) 4 (B) 5 (C) 6 (D) 7解：本题题意叙述虽长，但转换成图表语言， 则非常简洁. 如右图，即可选(A).例2集合A含有5个元素，B含3个元素 若从A到B可有多少个不同映射？ 若从B到A可有多少个不同映射？分析

2、：要建立一个从A到B的映射，必须使A中的任意一个元素在B中都有唯一的象，一般要分步考虑；同理可解决B到A的映射解： A中的任一元素去选择象都有3种方法 ，且要完成一个映射应该使A中的每一个元素都能找到唯一的象，由分步计数原理知：共有3×3×3×3×33243个同理可得从B到A可有5125个不同映射评注：一般地，对于集合A中有n个元素，B中有m个元素，则可建立A到B的映射35mn个映射二、特殊型映射的计数问题是指特殊的映射即满射、单射、一一映射、函数等的计数问题例3 我们称映射f：AB为一个“满射”，如果集合B中任意一个元素都有原象的话，已知集合A中含有4

3、个元素，B中含有3个元素，则这样不同满射的个数为( )(A) 24 (B) 81 (C) 64 (D) 36解：由题意可知，A中必有两个元素的象是B中的一个元素，而A中的另两个元素与B23CA43中的另两个元素分别对应，因此，从A到B可确定的满射个数为·36，故应选(D)例3 我们称映射：f：AB为一个“单射”，如果集合A中不同的元素在集合B中有不同的象的话已知集合A0，1，2，3，B2，3，4，5，6f是A到B的单射，则这样的单射f的个数是_解：根据所给单射的定义，本题等价于4个不同的元素去占5个不同的位置，共有多4A5少种不同占法的问题，故所求的单射的个数为120例4 我们称映射

4、：f：AB为一个“一一映射”，如果对于A中不同的元素，在B中都有不同的元素与之对应，而且，对于B中的任何一个元素都有原象存在的话已知集合A1，2，3，4，Ba，b，c，d，设集合A到B的不同映射的个数为m，从集合A到Bm的不同的一一映射的个数为n，那么n等于( )(A) 4 (B) 8 (C) 163 (D) 323m4解：由m4256，由本题所给出的“一一映射”的定义可知nA24所以，n44323，故应选(D)三、限制型映射的计数问题是指在一般映射的基础上，添加约束条件这类问题灵活性和技巧性都很强，没有固定的解题模式可套，解题时应认真审视约束条件，常借助分类讨论的思想方法和排列组合的有关知识

5、使问题得以圆满解决例5 集合A1，2，3，B3，4，从A到B的映射f满足f(3)3，则这样的映射共有_个解：确定映射f的个数可分步如下：确定A中元素1的对应元，有2种办法；确定A中元素2的对应元，有2种办法所求的映射共有2×24(个).例6 设A1，2，则从A到A的映射中，满足ff(x)f(x)的个数是（ ）(A) 1 (B) 2 (C) 3 (D) 4解：从A到A的映射中，满足ff(x)f(x)，有f(x)1，f(x)2，f(x)x，xA，共有3个故选(C)例7已知集合Aa，b，c，B1，0，1，由A到B的映射f满足f(a)f( b)f(c)，那么这样的映射的个数是( )(A)4

6、(B)5 (C)6 (D)7分析：这里的f(a)，f( b)，f(c)B，且f(a)f( b)f(c)，故可分类讨论解：根据映射的概念进行分类讨论：当f(c)1时，则f(a)1，f(b)0或f(a)0，f(b)1，共2种；当f(c)0时，则f(a)1，f(b)1或f(a)0，f(b)0或f(a)1，f(b)1，共3种；当f(c)1时，则f(a)1，f(b)0或f(a)0，f(b)1，共2种综上可知，符合条件的共有2327种，选(D)例8 设集合A1，2，3，4，5，B6，7，8，从A到B的映射f中，满足f(1)f(2)f(3)f(4)f(5)的映射的个数是( )(A)3 (B)6 (C)12

7、(D)21解法1：因为B中只有3个元素，所以f(1)f(2)f(3)f(4)f(5)中的4个不等1C号，至多有两个取不等号，没有不等号的映射(即只与B中同一个元素对应) f有33个；12CC43有一个不等号的映射(即与B中两个元素对应) f有·=12个；有两个不等号的映射(即23CC4与B中三个元素对应) f有·36个所以共有312621个符合要求的映射故应选(D)解法2：由题意，满足f(1)f(2)f(3)f(4)f(5)，即满足6f(1)f(2)f(3)f(4)f(5)8；而每一个满足的映射都唯一对应着一个6f(1)1f(2)2f(3)3f(4)4f(5)512的映射；

8、5C7于是问题相当于从6到12这7个整数任取5个整数的取法数，即满足题意的映射有21个例9 设集合Aa，b，c，d，B1，2，3，从A到B建立映射f，使f(a)f(b)f(c)f(d)8，则满足条件的映射f共有_个132CCC44解：8222232213311，则共有1·419个符合要求的映射例10 设集合M1，0，1，N1，2，3，4，5，映射f：MN，使对任意xM，都有xf(x)xf(x)为奇数，这样的映射f的个数为_分析 关键是读懂题意，其中的条件限制“xf(x)xf(x) 是奇数”，意思是“原象加象再加上原象与象的乘积是奇数”解：分三步：1去选象，此时xf(x)xf(x)x1

9、，一定是奇数，故1的象有五种；0选象，此时xf(x)xf(x)f(x)，故0的象有“1，3，5”三种；1选象，此时xf(x)xf(x)x2f(x)12f(x)，因而2f(x)肯定是偶数，所以1的象有五种由乘法原理知：共有5×3×575个满足题意的映射四、转化型映射的计数问题是指灵活运用映射知识，则能转化为映射的计数问题，从而突破解题难点，优化解题思路，甚至能避免分类讨论等例11 有100名选手参加乒乓球赛，赛制是淘汰制，问需要安排多少场比赛决出冠军？ 分析：用常规方法，需分多轮进行，即分类相加，非常繁而用映射方法，则显得简捷快速解：一场比赛对应一个失败者(淘汰者)，要决出冠

10、军必须淘汰99人(包括亚军)，故要进行99场比赛例12 厂家为回收空瓶，规定3个空瓶可换一瓶啤酒，有人订购10瓶啤酒，问此人能喝几瓶啤酒？分析：用常规方法，往往错认为是可喝14瓶，剩2个空瓶，其实应为15瓶，先到商家借1个空瓶，凑成3个空瓶，再喝完将空瓶还给商家也就是体现数学中“添0法”，即“011”解：由题意，得3个空瓶对应一瓶啤酒(含瓶)，即2个空瓶对应一瓶量的啤酒(不含瓶)，如图故10瓶啤酒10瓶量的啤酒10瓶空瓶10瓶量的啤酒瓶量的啤酒15瓶量的啤酒所以可喝15瓶啤酒例13 求方程x1x2x3x47有多少组非负整数解解：把该方程的非负整数解的集合记作X，把7个球放在四个盒子中的总放法的

11、集合记Y因方程的每一组解如(3，3，1，0)对应一种放法，即7个球给第1、第2、第3、第4盒子分别放入3，3，1，0个球，如上对应作映射f：XY，则不同的解对应于不同的放法，反之不同的放法也有不同的解与之对应故f是一个一一映射，从而有集合X的元素与集7C10合Y的元素个数相等，由排列组合中“隔板法”知120故方程的非负整数解有120组例14 对集合A1，2，3，2001及每一个非空子集，定义一个唯一确定的“交替和”如下：按照递减的次序重新排列该子集，然后从最大的数开始，交替的减或加后继的数所得的结果。例如，集合1，2，4，7，10的“交替和”为1074216，集合7，10的“交替和”为1073，5的“交替和”为5，等等，试求A的所有子集的“交替和”的总和解：集合A1，2，3，2001的子集中，除了集合2001，还有220012个非空子集将其分为两类，第一类是含2001的子集，第二类是不含2001的子集，而且这两类各自所含子集的全体相互构成一一映射，从而这两类所含子集的个数相同因为若Ai是第二类的