特殊映射的計數研究

李長悅 (吉林師范大學，吉林 長春 130000)

一、引 言

我們在各種領域都會遇到對有限集的計數問題，而要想解決這些問題，我們需要掌握好基礎知識，還需要掌握一些計算的技巧.計數問題分為一般型映射、特殊型映射、限制型映射及轉化型映射等，本文主要研究一些特殊型映射的計數問題，即單射、滿射、雙射、函數等的計數問題.

二、基本概念

二十世紀八十年代初，代數的集合和映射的概念在中學數學教科書上已出現.在人民教育出版社1983年版的《代數(甲種本)》中可以看到有關“A到B上一一映射”的概念，它主要指的是“集合A中不同的元素在集合B中不同的象”，而且“B中的每一個元素都有原象”的映射.其實，后者正是指“一一映射”，前者則代表著“A到B上”的概念，但它并沒有具體地討論什么是“A到B上的映射”和什么是“一一映射”.

集合A到集合B的映射f:A→B，包括單射、滿射、雙射.單射指當x1,x2∈A，且x1≠x2時，B中元素f(x1)≠f(x2)，這種情況也被稱為一一映射，也有寫作1—1映射的.滿射是指f(A)=B，也稱A到B上的映射，或稱f是映射.雙射指既是單射又是滿射的映射，又稱“A到B上的一一映射”，或稱“A與B之間的一一對應”.特別地，有A到B上的一一映射 (既是滿射又是單射)，也可以有A到B內的一一映射 (不是滿射的單射).所以把A到B上的一一映射 (即雙射) 簡稱為一一映射 (通常指單射) 是不恰當的.

各種數學專業書籍，包括基礎教科書和一些專著，其中提到“一一映射”或“映射是一一的”(one to one或one—one，1—1) 均指單射，而“一一對應”指的是雙射.

(一)基礎知識

定義1設兩個非空集合X,Y，若存在一個映射之間的對應規則f，使得?x∈X，有唯一確定的y∈Y與之對應，則稱f為從X到Y的映射，記作f:X→Y.

圖1

(1)元素y是元素x在映射f下的象，記作y=f(x).

(2)元素x是元素y在映射f下的原象.

(3)集合X是映射f的定義域，Y的子集Rf=f(x)={f(x)|x∈X}是f的值域.

注意：①映射的三要素——定義域、對應規則、值域.

②元素x的象y是唯一的，但y的原象不一定唯一.

對于映射f:X→Y：

(1)若f(x)=Y，則稱f為滿射，如圖2所示.

圖2

(2)若?x1,x2∈X,x1≠x2，有f(x1)≠f(x2)，則稱f為單射，如圖3所示.

圖3

若f既是滿射又是單射，則稱f為雙射或一一映射.

說明映射在不同數學分支中有不同的慣用名，具體表示如下：

定義2把X到Y的映射叫作定義在X上、取值在Y內的函數.

定義3單射、滿射、雙射：有兩個集合X和Y，若對每一個x∈X，有y∈Y與之對應，那么就定義了一個從X到Y的映射f：X→Y.若由x1≠x2，得f(x1)≠f(x2)，則稱f為單射.若{f(x)|x∈X}=Y，則稱f為滿射.若f既是單射又是滿射，則稱f為X到Y上的一一映射，也稱雙射.

(二)雙射的條件

1.函數f:X→Y為雙射，當且僅當對?y∈Y，存在唯一的x∈X，滿足f(x)=y.

2.函數f:X→Y為雙射，當且僅當此函數可逆，即存在函數g:Y→X，滿足gf=X上的恒等函數，且gf為Y上的恒等函數.

3.兩個雙射復合也是雙射，如gf為雙射，則僅能得出f為單射且g為滿射.

三、映射的計數

(一)基本定理

映射原理設A和B都是有限集，f為從A到B的一個映射：

(1)如果f為單射，則|A|≤|B|；

(2)如果f為滿射，則|A|≥|B|；

(3)如果f為雙射，則|A|=|B|.(|A|代表A中元素的個數，下同)

同樣地，設A和B是兩個有限集合：

(1)|A|=m,|B|=n，則A到B的不同映射有nm個；

(4)|A|=m,|B|=n，當m=n時，A到B的雙射有n!個.

(二)映射的計數問題

1.單射的計數(排列)

我們首先要構造一個理想的典型模型：筆放到盒子里.例如：把黑、白2支筆放到紅色盒子、藍色盒子、黃色盒子中(這里的黑、白色筆指的是筆身的顏色，下同)，如果假設每個盒子里只能放1支筆，那么將這2支筆放到盒子中有多少種不同的安排?我們是這樣思考的：不妨設先把白筆放到3個盒子的任何一個中，其次放黑筆，放到剩下2個盒子的任何一個中，因此，2支筆放到3個盒子中的不同方式的種數為3×2=6.

我們把這個問題用現代數學語言——映射來表達.

不妨先將盒子分別編號為1，2，3，把3個不同顏色的盒子當作3個位置，把2支筆看作2件東西，這是東西與位置間的一種對應，本例中由于筆少盒子多，因而是單射.

這種單射可以表示為：

f1={(白，1)，(黑，2)}，f2={(白，1)，(黑，3)}，

f3={(白，2)，(黑，1)}，f4={(白，2)，(黑，3)}，

f5={(白，3)，(黑，1)}，f6={(白，3)，(黑，2)}.

也可如圖4所示.

圖4

上述例題中的特殊數字不難推廣到一般情況：

下面用映射的語言進行表示：

設A={1,2,…,m}，即Nm表示m個元素的一個集合，于是B={1,2,…,n}.

I(A,B)表示從A到B的所有單射，#(A,B)表示從A到B的所有單射的個數.

2.雙射的計數(組合)

在上面“筆放到盒子里”的舉例中，有兩種筆——黑筆、白筆，倘若將白筆涂成黑色，則2支筆都是黑筆，這樣就意味著無序(與順序無關)投入.于是放筆入盒的問題簡化為：將2支筆分別投入不同的3個盒子中，并使一個盒子至多只能放1支筆，則共有三種單射：s1={(黑，1)，(黑，2)}，s2={(黑，1)，(黑，3)}，s3={(黑，2)，(黑，3)}.

圖5

現在回顧排列中的6個單射，其中f1={(白，1)，(黑，2)}，f3={(白，2)，(黑，1)}，由于“白筆”即“黑筆”，因此f1，f3與s1看作相同，同理，f2，f5與s2以及f4，f6與s3也分別是一樣的.通常情況下，若有從A到B的排列中的兩個單射h,g，即h,g∈I(A,B)，若Im(h)=Im(g)，即兩個單射h與g的“象”相同，不管它們的排列順序是怎樣的，都把它們看作同一個組合.

這樣，把所有具有等價關系的單射放在一起，形成等價類，例如，f1≈f3是同一類，類似地，f2≈f5,f4≈f6也分別看作同一類.

3.滿射的計數

下面建立滿射的計數公式:

顯然：(1)若n

現設m≥n，滿射f:A→B的

證明設A={x1,x2,…,xm},B={y1,y2,…,yn},f:A→B，yi不屬于集合A中的任何一個元素的象的映射構成的集合Ai,i=1,2,…,n，即Ai={f:A→B|yi?Im(f)}，則A到B的所有滿射個數為：

S=nm-|A1∪A2∪…∪An|

四、關于特殊映射計數問題的探究

問題已知兩個集合A={1,2,3,4}與B={a,b,c,d,e}，f(A)∈{a,b,c,d,e},設a

探究1若改變f(1)≤f(2)

變式1若將“f(1)≤f(2)

于是有：

探究2改變f(1)≤f(2)

變式2如果將“f(1)≤f(2)

探究3同時改變“≤”所在的位置及使用的個數，會有什么樣的結論?

變式3若將“f(1)≤f(2)

綜上，有如下結論：

探究4能否將結論1，2形式上的結果通過一定的轉化變為相同的?再比較一下得出的相對應的兩個結果，看看是否能發現一些規律.

五、計數問題在中學數學中的應用

例1數集A={a1,a2,…,a100}，數集B={b1,b2,…,b50}，映射f:A→B滿足f(a1)≤f(a2)≤…≤f(a100)的映射有多少個?

例2設M={a,b,c},N={-3,0,5}.

(1)求映射的個數；

(2)若集合M到N的映射f滿足f(a)>f(b)≥f(c)，試求f的個數.

解(1)根據映射的基本要求“每個元素必有對應的象，每個對應的象必是唯一的”，在集合M中，元素a可以對應N中的任意一個元素，這樣就會產生3種對應方法.同理，M中元素b，c也各有3種不同的對應方法.所以，由乘法原理可知，從M到N的映射個數為33=27.

(2)滿足f(a)>f(b)≥f(c)的映射是從M到N的特殊映射，具體情況如下表所示：

f(a)f(b)f(c)0-3-35-3-350-3500

故符合條件的映射個數為4.

分析若在沒有限制條件的情況下求映射的個數，可直接采用乘法原理.若有限制條件且數目不大，可利用列舉法或列表法轉化成圖表語言.

例3映射f:{a,b,c,d}→{0,1,2,4}中，滿足f(a)+f(b)+f(c)+f(d)=4的映射有多少個?

解f(a)+f(b)+f(c)+f(d)=4有以下4種情況：

綜上所述，滿足f(a)+f(b)+f(c)+f(d)=4的映射共有4+6+12+1=23(個).

六、結 語

映射是中學數學中一個基本且重要的概念，它不僅為函數的學習奠定了基礎，而且自身有非常鮮明的特點.由于兩個集合之間可能有不同的映射類型，所以產生了排列組合的相互聯系，也就是映射的計數問題，因此，映射計數問題的類型很豐富，值得我們去探索和挖掘其中的奧秘.本文通過對競賽和高考中各種類型的映射計數問題進行分析，以期讀者對映射計數的相關原理更加清晰.