映射觀下的排列問題

陳 明

（遵義師范學(xué)院數(shù)學(xué)系，貴州遵義563002）

排列問題是中學(xué)數(shù)學(xué)內(nèi)容中的一個難點，主要表現(xiàn)在學(xué)生對其定義及表述難以理解，對解題思路及方法難以掌握。中學(xué)數(shù)學(xué)教材對排列問題的處理方式毫無異議，它主要是根據(jù)學(xué)生的認(rèn)知特征來確定的，但作為教師自身僅限于此是遠(yuǎn)不夠的，還應(yīng)用現(xiàn)代數(shù)學(xué)的觀點去揭示它，即弄清它的理論本質(zhì)。為此，本文用集合、單射、計數(shù)的觀點對排列進(jìn)行了較深層次的闡釋，不僅說明了現(xiàn)代數(shù)學(xué)與中學(xué)數(shù)學(xué)在這一部分內(nèi)容的內(nèi)在聯(lián)系，而且有助于教師對該問題的認(rèn)識。

文中所討論的集合均為有限集。為方便，記#A表示集合 A 的元素個數(shù)，Nn=｛1，2，…，n｝表示從 1 開始的n個自然數(shù)的集合，I（Nm，A）表示映集Nm到集A所有單射組成的集合。關(guān)于集合的映射計數(shù)法，可作如下定義。

定義 若#A=n，當(dāng)且僅當(dāng)存在著一個雙射f∶A→Nn。

顯然，若 #A=?，當(dāng)且僅當(dāng) #A=0。

在定理的證明中，本文用到了如下引理。

引理[1]若函數(shù) f∶B→D，h∶C→A 均為雙射，則有等價I（A，D）≈I（C，B）

眾所周知，排列問題乃計數(shù)問題，而在集合論中，運用映射計數(shù)是較為典型的思想方法，為闡明排列問題與映射的關(guān)系，先看一個簡單的例子。

例1有5本不同的書，準(zhǔn)備分給3名同學(xué)，每人1本，共有多少種給法？

將三名同學(xué)編號為1，2，3，他們組成集合N3=｛1，2，3｝。同樣，5 本不同的書組成集合 A=｛a1，a2，a3，a4，a5｝。對任意一種給法：如 a5給 1；a3給 2；a1給 3，唯一確定由N3到A的一個單射（如圖1）。

圖1 N3到A的一個單射 圖2 N3到A的任一單射

反之，由N3到A的任一單射（如圖2），同樣也唯一地確定了一種給法：a2給 1；a4給 2；a3給 3。

由此可看出，“給法”與I（N3，A）之間具有一一對A）。將這一結(jié)論推廣，得到定理1。

從而，計算#I（Nm，A）就轉(zhuǎn)化為計算#I（Nm，Nn）了。

下面對m分m=0和1≤m≤n兩種情況討論如下：

（1）若 m=0，有

且對?θ∈I（Nm，Nn），定義ν（θ）?θ│Nm-1。

由于θ是一對一的，所以，ν（θ）也是一對一的。故?θ∈I（Nm-1，Nn）。因此，ν的定義是有意義的。

現(xiàn)不妨設(shè)φ為I（Nm-1，Nn）中的任一元，且對應(yīng)關(guān)系（如圖 3），（其中 ai∈Nn）

圖3 φ的對應(yīng)關(guān)系

圖4 θ的對應(yīng)關(guān)系

顯然，φ是圖4中映射θ在Nm-1上的限制，故φ=θ│Nm-1，而 θ 又顯然是屬于 I（Nm，Nn）的，所以，ν是在上的。

另外，由圖 4 顯見，當(dāng) θ（m）對應(yīng)｛am，am+1，…，an｝中n-m+1個的每一個時，得到I（Nm，Nn）中的n-m+1個單射。即是說I（Nm，Nn）中有n-m+1個單射在Nm-1上的限制都是φ，從而可推得φ具有如下的性質(zhì)：

故當(dāng)φ取遍I（Nm-1，Nn）時，I（Nm，Nn）就是諸集合ν-1｛φ｝的并。

顯然，諸集合ν-1｛φ｝是互不相交的。

事實上，若給定 I（Nm，Nn）上的一個關(guān)系 R，對?h，k∈I（Nm，Nn），h R k，當(dāng)且僅當(dāng) h，k 在 Nm-1上的限制相同。易證R是一個等價關(guān)系。從而R確定I（Nm，Nn）上的一個劃分，并將其劃分為諸陪集 I（Nm，Nn）/R。這樣諸集合ν-1｛φ｝實質(zhì)上就是諸陪集。當(dāng)然它們是互不相交的。

又由于 φ 共有 #I（Nm，Nn）=Am-1n多個，所以諸集合ν-1｛φ｝也就有Am-1n個，故由（1）式有

以上各式左右分別相乘，化簡得

例2用0～9這十個數(shù)字，可以組成多少個沒有重復(fù)數(shù)字的三位數(shù)？

我們從如下的角度去考慮，設(shè)集合P=｛0，1，2，…，9｝，并視其為具有 十個位置的“位置”集合。令A(yù)=｛Ⅰ，Ⅱ，Ⅲ｝，其中Ⅰ，Ⅱ，Ⅲ分別表示一個三位數(shù)的首位、中位和末位數(shù)字。這樣，一個三位數(shù)就可以視為用A中的元去占有“位置”集合P的三個“位置”。從而，每一個確定的三位數(shù)就定義了一個單射f∶A→P，其中f（i），i=Ⅰ、Ⅱ、Ⅲ是在P中被i所占有的位置。因Ⅰ，Ⅱ，Ⅲ中任兩個不可能占據(jù)同一位置，因而f是一對一的。于是有

又據(jù)題意Ⅰ不能占據(jù)“0位置”，而Ⅰ占據(jù)“0位置”的共有A29種，同上分析有

計算得

因此，可組成648個沒有重復(fù)數(shù)字的三位數(shù)。

類似以上占據(jù)“位置”的事例在日常生活中無處不見。如：影劇院中觀看電影的人；書架上的書；計算機(jī)中的內(nèi)存貯等，不勝枚舉。采用定理1的方法，可將現(xiàn)實排列問題轉(zhuǎn)化為數(shù)集間單映射的個數(shù)問題，使問題變得簡潔，并且有規(guī)律可循，這也正是現(xiàn)代數(shù)學(xué)同構(gòu)思想的一個體現(xiàn)。

[1]H·B格里菲思，P·U希爾頓．經(jīng)典數(shù)學(xué)綜合教材[M]．陳應(yīng)樞，陳信傳譯．貴州：貴州人民出版社，1986．

[2]張奠宙，鄒一心．現(xiàn)代數(shù)學(xué)與中學(xué)數(shù)學(xué)[M]．上海：上海教育出版社，1990．

[3]陳明．排列組合之加法原理探索[J]．貴州師范大學(xué)學(xué)報，2007，（2）：199-200．

[4]陳明．排列組合之乘法原理探索[J]．黔南民族師范學(xué)院學(xué)報，2007，（6）：37-38．