特殊映射的計數(shù)研究

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

一、引 言

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

二、基本概念

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

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

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

(一)基礎(chǔ)知識

定義1設(shè)兩個非空集合X,Y，若存在一個映射之間的對應(yīng)規(guī)則f，使得?x∈X，有唯一確定的y∈Y與之對應(yīng)，則稱f為從X到Y(jié)的映射，記作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的值域.

注意：①映射的三要素——定義域、對應(yīng)規(guī)則、值域.

②元素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為雙射或一一映射.

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

定義2把X到Y(jié)的映射叫作定義在X上、取值在Y內(nèi)的函數(shù).

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

(二)雙射的條件

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

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

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

三、映射的計數(shù)

(一)基本定理

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

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

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

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

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

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

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

(二)映射的計數(shù)問題

1.單射的計數(shù)(排列)

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

我們把這個問題用現(xiàn)代數(shù)學(xué)語言——映射來表達(dá).

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

這種單射可以表示為：

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

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

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

也可如圖4所示.

圖4

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

下面用映射的語言進(jìn)行表示：

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

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

2.雙射的計數(shù)(組合)

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

圖5

現(xiàn)在回顧排列中的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的“象”相同，不管它們的排列順序是怎樣的，都把它們看作同一個組合.

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

3.滿射的計數(shù)

下面建立滿射的計數(shù)公式:

顯然：(1)若n

現(xiàn)設(shè)m≥n，滿射f:A→B的

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

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

四、關(guān)于特殊映射計數(shù)問題的探究

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

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

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

于是有：

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

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

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

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

綜上，有如下結(jié)論：

探究4能否將結(jié)論1，2形式上的結(jié)果通過一定的轉(zhuǎn)化變?yōu)橄嗤?再比較一下得出的相對應(yīng)的兩個結(jié)果，看看是否能發(fā)現(xiàn)一些規(guī)律.

五、計數(shù)問題在中學(xué)數(shù)學(xué)中的應(yīng)用

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

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

(1)求映射的個數(shù)；

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

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

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

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

故符合條件的映射個數(shù)為4.

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

例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(個).

六、結(jié) 語

映射是中學(xué)數(shù)學(xué)中一個基本且重要的概念，它不僅為函數(shù)的學(xué)習(xí)奠定了基礎(chǔ)，而且自身有非常鮮明的特點.由于兩個集合之間可能有不同的映射類型，所以產(chǎn)生了排列組合的相互聯(lián)系，也就是映射的計數(shù)問題，因此，映射計數(shù)問題的類型很豐富，值得我們?nèi)ヌ剿骱屯诰蚱渲械膴W秘.本文通過對競賽和高考中各種類型的映射計數(shù)問題進(jìn)行分析，以期讀者對映射計數(shù)的相關(guān)原理更加清晰.