一般型映射的计数问题doc

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

2、 A 可有多少个不同映射？分析： 要建立一个从A到 B 的映射，必须使A 中的任意一个元素在B中都有唯一的象，一般要分步考虑；同理可解决B到 A的映射解： A 中的任一元素去选择象都有3 种方法，且要完成一个映射应该使A 中的每一个元素都能找到唯一的象，由分步计数原理知：共有3× 3× 3× 3× 3 35 243 个同理可得从 B 到 A 可有 53 125 个不同映射评注：一般地，对于集合A中有n个元素，B中有 个元素，则可建立A到B的映射mnm 个映射二、特殊型映射的计数问题是指特殊的映射即满射、单射、一一映射、函数等的计数问题例 3 我们称映射

3、f ：A B为一个“满射”，如果集合B 中任意一个元素都有原象的话，已知集合 A中含有 4 个元素， B 中含有 3个元素，则这样不同满射的个数为()(A) 24(B) 81(C) 64(D) 36解： 由题意可知， A 中必有两个元素的象是 B 中的一个元素，而A 中的另两个元素与 B中的另两个元素分别对应，因此，从 A 到 B 可确定的满射个数为C42· A33 36，故应选 (D) 例 3 我们称映射： f ： A B 为一个“单射”，如果集合A 中不同的元素在集合B中有不同的象的话已知集合A 0 ， 1，2， 3 ，B 2 ，3， 4，5， 6 f 是 A 到 B 的单射，则

4、这样的单射 f 的个数是 _解：根据所给单射的定义，本题等价于4 个不同的元素去占5 个不同的位置，共有多少种不同占法的问题，故所求的单射的个数为A 54 120例 4 我们称映射：f： 为一个“一一映射”，如果对于A中不同的元素，在B中A B都有不同的元素与之对应，而且，对于B 中的任何一个元素都有原象存在的话已知集合A1 ，2，3， 4， ， ， ，设集合A到B的不同映射的个数为，从集合A到BB a b cdmm的不同的一一映射的个数为n，那么 n 等于 ()(A) 4(B) 8(C) 163(D) 323n A 44m解：由 m44 256，由本题所给出的“一一映射”的定义可知 24所以

5、， n 323，故应选 (D) 三、限制型映射的计数问题是指在一般映射的基础上，添加约束条件这类问题灵活性和技巧性都很强，没有固定的解题模式可套，解题时应认真审视约束条件，常借助分类讨论的思想方法和排列组合的有关知识使问题得以圆满解决例 5 集合 A 1 ，2， 3 ，B 3 ，4 ，从 A 到 B的映射 f 满足 f (3) 3，则这样的映射共有 _个解：确定映射 f 的个数可分步如下：确定A 中元素 1 的对应元，有2 种办法；确定 A 中元素 2 的对应元，有 2 种办法所求的映射共有 2× 2 4( 个 ).例6设 A1 ， 2 ，则从A 到 A 的映射中，满足f f ( x

6、)f ( x) 的个数是（）(A) 1(B) 2(C) 3(D) 4解：从A 到A的映射中，满足f f ( x) f ( x) ，有f ( x) 1，f ( x) 2，f ( x) x，x A，共有3 个故选(C) 例 7 已知集合 A a， b， c ， B1 ， 0， 1 ，由 A 到 B 的映射 f 满足 f ( a) f ( b) f ( c) ，那么这样的映射的个数是 ()(A)4(B)5(C)6(D)7分析： 这里的f(a) ，(b) ，f(c) ，且f(a) (b) (c) ，故可分类讨论fBff解： 根据映射的概念进行分类讨论：当f(c)1 时，则f( )1，f()0或f( )

7、0，f( )1，共 2种；abab当 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() 0，() 1，共 2 种afb综上可知，符合条件的共有2 3 2 7 种，选 (D) 例8 设集合1 ，2，3，4， 5， 6 ，7， 8 ，从A到B的映射f中，满足f(1)AB f(2) f(3) f (4)f (5)的映射的个数是 ()(A)3(B)6(C)12(D)21解法 1：因为 B 中只有 3 个元素，所以f(1) f(2)f(3) f(

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

9、 (1) 1 f (2) 2 f (3) 3 f (4) 4 f (5) 5 12 的映射；于是问题相当于从6到 12这 7个整数任取5 个整数的取法数， 即满足题意的映射有C75 21 个例 9 设集合 A a， b，c， d ， B 1 ， 2，3 ，从 A 到 B 建立映射 f ，使 f ( a) f ( b) f ( c) f ( d) 8，则满足条件的映射f 共有 _个解： 8 22 2 23 2 21 3 3 1 1，则共有 1 C14 · C34 C24 19 个符合要求的映射例 10 设集合 M 1， 0， 1 ， N 1 ， 2，3， 4，5 ，映射 f ： M N

10、，使对任意 x M，都有 x f ( x) xf ( x) 为奇数，这样的映射 f 的个数为 _分析 关键是读懂题意，其中的条件限制“x f ( x) xf ( x) 是奇数”，意思是“原象加象再加上原象与象的乘积是奇数”解：分三步： 1 去选象，此时x f ( x) xf ( x) x 1，一定是奇数，故 1 的象有五种； 0 选象，此时 x f ( x) xf ( x) f ( x) ，故 0 的象有“ 1， 3， 5”三种； 1 选象，此时 x f ( x) xf ( x) x 2f ( x) 12f ( x) ，因而 2f ( x) 肯定是偶数，所以 1 的象有五种由乘法原理知：共有5

11、× 3× 5 75 个满足题意的映射四、转化型映射的计数问题是指灵活运用映射知识，则能转化为映射的计数问题，从而突破解题难点，优化解题思路，甚至能避免分类讨论等例 11 有 100 名选手参加乒乓球赛，赛制是淘汰制， 问需要安排多少场比赛决出冠军？分析： 用常规方法，需分多轮进行，即分类相加，非常繁而用映射方法，则显得简捷快速解： 一场比赛对应一个失败者( 淘汰者 ) ，要决出冠军必须淘汰99 人 ( 包括亚军 ) ，故要进行 99 场比赛例 12 厂家为回收空瓶，规定3 个空瓶可换一瓶啤酒，有人订购10 瓶啤酒，问此人能喝几瓶啤酒？分析： 用常规方法，往往错认为是可喝14

12、 瓶，剩 2 个空瓶，其实应为15 瓶，先到商家借 1 个空瓶，凑成3 个空瓶，再喝完将空瓶还给商家也就是体现数学中“添0 法”，即“ 0 1 1”解：由题意，得 3 个空瓶对应一瓶啤酒( 含瓶 ) ，即 2 个空瓶对应一瓶量的啤酒( 不含瓶 ) ，如图故 10 瓶啤酒 10 瓶量的啤酒 10 瓶空瓶 10 瓶量的啤酒瓶量的啤酒15 瓶量的啤酒所以可喝15 瓶啤酒例 13 求方程 x1 x2 x3 x4 7 有多少组非负整数解解：把该方程的非负整数解的集合记作X，把 7 个球放在四个盒子中的总放法的集合记因方程的每一组解如 (3 ，3，1，0) 对应一种放法，即7 个球给第 1、第 2、第 3

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