映射的計數(shù)問題(經(jīng)典)

1、一、一般型映射的計數(shù)問題是指課本中介紹的映射知識，這類問題常涉及有求元素個數(shù)、集合個數(shù)、映射個數(shù)等，較簡單的可用枚舉法、圖表法、分類討論法，適當時要借助于排列組合的知識 例1(2000年全國高考題) 已知映射f：AB，其中，集合A3，21，1，2，3，4，集合B中的元素都是A中元素在映射f下的象，且對任意的aA，在B中和它對應的元素是|a|，則集合B中元素的個數(shù)是( )(A) 4 (B) 5 (C) 6 (D) 7解：本題題意敘述雖長，但轉(zhuǎn)換成圖表語言， 則非常簡潔. 如右圖，即可選(A).例2集合A含有5個元素，B含3個元素 若從A到B可有多少個不同映射？ 若從B到A可有多少個不同映射？分析

2、：要建立一個從A到B的映射，必須使A中的任意一個元素在B中都有唯一的象，一般要分步考慮；同理可解決B到A的映射解： A中的任一元素去選擇象都有3種方法 ，且要完成一個映射應該使A中的每一個元素都能找到唯一的象，由分步計數(shù)原理知：共有3×3×3×3×33243個同理可得從B到A可有5125個不同映射評注：一般地，對于集合A中有n個元素，B中有m個元素，則可建立A到B的映射35mn個映射二、特殊型映射的計數(shù)問題是指特殊的映射即滿射、單射、一一映射、函數(shù)等的計數(shù)問題例3 我們稱映射f：AB為一個“滿射”，如果集合B中任意一個元素都有原象的話，已知集合A中含有4

3、個元素，B中含有3個元素，則這樣不同滿射的個數(shù)為( )(A) 24 (B) 81 (C) 64 (D) 36解：由題意可知，A中必有兩個元素的象是B中的一個元素，而A中的另兩個元素與B23CA43中的另兩個元素分別對應，因此，從A到B可確定的滿射個數(shù)為·36，故應選(D)例3 我們稱映射：f：AB為一個“單射”，如果集合A中不同的元素在集合B中有不同的象的話已知集合A0，1，2，3，B2，3，4，5，6f是A到B的單射，則這樣的單射f的個數(shù)是_解：根據(jù)所給單射的定義，本題等價于4個不同的元素去占5個不同的位置，共有多4A5少種不同占法的問題，故所求的單射的個數(shù)為120例4 我們稱映射

4、：f：AB為一個“一一映射”，如果對于A中不同的元素，在B中都有不同的元素與之對應，而且，對于B中的任何一個元素都有原象存在的話已知集合A1，2，3，4，Ba，b，c，d，設(shè)集合A到B的不同映射的個數(shù)為m，從集合A到Bm的不同的一一映射的個數(shù)為n，那么n等于( )(A) 4 (B) 8 (C) 163 (D) 323m4解：由m4256，由本題所給出的“一一映射”的定義可知nA24所以，n44323，故應選(D)三、限制型映射的計數(shù)問題是指在一般映射的基礎(chǔ)上，添加約束條件這類問題靈活性和技巧性都很強，沒有固定的解題模式可套，解題時應認真審視約束條件，常借助分類討論的思想方法和排列組合的有關(guān)知識

5、使問題得以圓滿解決例5 集合A1，2，3，B3，4，從A到B的映射f滿足f(3)3，則這樣的映射共有_個解：確定映射f的個數(shù)可分步如下：確定A中元素1的對應元，有2種辦法；確定A中元素2的對應元，有2種辦法所求的映射共有2×24(個).例6 設(shè)A1，2，則從A到A的映射中，滿足ff(x)f(x)的個數(shù)是（ ）(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)，那么這樣的映射的個數(shù)是( )(A)4

6、(B)5 (C)6 (D)7分析：這里的f(a)，f( b)，f(c)B，且f(a)f( b)f(c)，故可分類討論解：根據(jù)映射的概念進行分類討論：當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 設(shè)集合A1，2，3，4，5，B6，7，8，從A到B的映射f中，滿足f(1)f(2)f(3)f(4)f(5)的映射的個數(shù)是( )(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個整數(shù)任取5個整數(shù)的取法數(shù)，即滿足題意的映射有21個例9 設(shè)集合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 設(shè)集合M1，0，1，N1，2，3，4，5，映射f：MN，使對任意xM，都有xf(x)xf(x)為奇數(shù)，這樣的映射f的個數(shù)為_分析 關(guān)鍵是讀懂題意，其中的條件限制“xf(x)xf(x) 是奇數(shù)”，意思是“原象加象再加上原象與象的乘積是奇數(shù)”解：分三步：1去選象，此時xf(x)xf(x)x1

9、，一定是奇數(shù)，故1的象有五種；0選象，此時xf(x)xf(x)f(x)，故0的象有“1，3，5”三種；1選象，此時xf(x)xf(x)x2f(x)12f(x)，因而2f(x)肯定是偶數(shù)，所以1的象有五種由乘法原理知：共有5×3×575個滿足題意的映射四、轉(zhuǎn)化型映射的計數(shù)問題是指靈活運用映射知識，則能轉(zhuǎn)化為映射的計數(shù)問題，從而突破解題難點，優(yōu)化解題思路，甚至能避免分類討論等例11 有100名選手參加乒乓球賽，賽制是淘汰制，問需要安排多少場比賽決出冠軍？ 分析：用常規(guī)方法，需分多輪進行，即分類相加，非常繁而用映射方法，則顯得簡捷快速解：一場比賽對應一個失敗者(淘汰者)，要決出冠

10、軍必須淘汰99人(包括亞軍)，故要進行99場比賽例12 廠家為回收空瓶，規(guī)定3個空瓶可換一瓶啤酒，有人訂購10瓶啤酒，問此人能喝幾瓶啤酒？分析：用常規(guī)方法，往往錯認為是可喝14瓶，剩2個空瓶，其實應為15瓶，先到商家借1個空瓶，湊成3個空瓶，再喝完將空瓶還給商家也就是體現(xiàn)數(shù)學中“添0法”，即“011”解：由題意，得3個空瓶對應一瓶啤酒(含瓶)，即2個空瓶對應一瓶量的啤酒(不含瓶)，如圖故10瓶啤酒10瓶量的啤酒10瓶空瓶10瓶量的啤酒瓶量的啤酒15瓶量的啤酒所以可喝15瓶啤酒例13 求方程x1x2x3x47有多少組非負整數(shù)解解：把該方程的非負整數(shù)解的集合記作X，把7個球放在四個盒子中的總放法的

11、集合記Y因方程的每一組解如(3，3，1，0)對應一種放法，即7個球給第1、第2、第3、第4盒子分別放入3，3，1，0個球，如上對應作映射f：XY，則不同的解對應于不同的放法，反之不同的放法也有不同的解與之對應故f是一個一一映射，從而有集合X的元素與集7C10合Y的元素個數(shù)相等，由排列組合中“隔板法”知120故方程的非負整數(shù)解有120組例14 對集合A1，2，3，2001及每一個非空子集，定義一個唯一確定的“交替和”如下：按照遞減的次序重新排列該子集，然后從最大的數(shù)開始，交替的減或加后繼的數(shù)所得的結(jié)果。例如，集合1，2，4，7，10的“交替和”為1074216，集合7，10的“交替和”為1073，5的“交替和”為5，等等，試求A的所有子集的“交替和”的總和解：集合A1，2，3，2001的子集中，除了集合2001，還有220012個非空子集將其分為兩類，第一類是含2001的子集，第二類是不含2001的子集，而且這兩類各自所含子集的全體相互構(gòu)成一一映射，從而這兩類所含子集的個數(shù)相同因為若Ai是第二類的