映射觀下的排列問題

陳 明

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

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

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

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

顯然，若 #A=?，當且僅當 #A=0。

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

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

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

例1有5本不同的書，準備分給3名同學，每人1本，共有多少種給法？

將三名同學編號為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）。將這一結論推廣，得到定理1。

從而，計算#I（Nm，A）就轉化為計算#I（Nm，Nn）了。

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

（1）若 m=0，有

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

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

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

圖3 φ的對應關系

圖4 θ的對應關系

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

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

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

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

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

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

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

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

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

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

計算得

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

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

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

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

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

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