淺談排列組合題解法

中圖分類號：G4

排列組合應用題是現行中學數學教學大綱的一項重要內容。遞推法是解排列組合應用題的一個重要方法，許多問題用這一方法來解顯得精練簡潔，并往往能得到解決同類問題的通用解法或得到一個應用較廣的遞推公式。

（1994年高考題）同室4人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀年卡，則4張賀年卡不同的拿法有

A.6種 B.9種 C.11種 D.23種

下面介紹包括“構造法”在內的5種解法。

1.構造法：構造法的關鍵是針對問題的實際意義，構造一個三棱錐，記這4個人為A，B，C，D，每人所寫的賀年卡對應記為a，b，c，d（如圖），設法把每個人和他寫出的賀年卡同放在三棱錐的一個頂點上，則4個頂點剛好分配完。規定每條棱表示2種順序拿法。例如棱AB表示A拿b或B拿a。根據題意全部拿法分為兩類：第一類是4人中有2人交換著拿，例如A拿b，B拿a，這時另2人也只能交換著拿，這種拿法在三棱錐中表示為成異面直線關系的兩條棱，而這樣的棱在三棱錐中共有3對，所以這類拿法有3種。第二類是4人順序循環拿，例如A拿b，B拿c，C拿d，D拿a（或反序循環：A拿d，D拿c，C拿b，B拿a），這在圖中表示為4條首尾順次相接的棱構成的空間四邊形ABCD。而余下的2條棱也恰好為1對“異面直線棱”。由于三棱錐中共有3對這樣的“異面直線棱”，所以圖中共有3個不同的空間四邊形，而每個四邊形有2種循環序表示2種拿法。故第二類拿法共有3×2=6種。因此，兩類拿法共表示9種不同的分配方式。

2.列舉法：當問題比較簡單時可做具體分析。

設4人A，B，C，D，寫的賀年卡分別記為a， b， c， d.

可從第一個人A考慮起，當A取b時，其他三人可

取的情況見右表。由表可知A取b 時有三種分配方

法。同樣A取c， d 時也各有三種方法。這樣由A的

取法可分三類，由加法原理，得 3+3+3=9（種）

3.直接法：用乘法原理。即讓四人依次拿一張賀年卡，分四步進行。

第一步：A先拿有3種方法；第二步：叫被A取走他寫的賀年卡的人再拿，也有三種取法；第三步：剩下的兩張賀年卡中至少有一張是還沒拿的兩個人中的某個人寫的，讓這個人拿只有一種拿法；第四步：一張賀年卡一個人只有一種拿法。

由乘法原理得：3×3×1×1=9（種）

4.間接法：先不考慮要求，四個人拿四張不同的賀年卡，每人一張的方法數為P44=24種，其中不合要求的情況有：

（1）四個人均拿到自己寫的賀年卡的情況：這種情況有1種。

（2）有且只有兩個人拿到自己寫的賀年卡的情況：有C42×1=6種。

（3）有且只有一個人拿到自己寫的賀年卡的情況：有C41×2=8種。

故共有：24-1-6-8=9（種）

“構造法”運用巧妙，但這種解法比較難思考，有較大的局限性，也比較難進一步推廣，假如把4個人改為5個人、6個人或更多的，用“構造法”恐怕很復雜。經深入研究和探討，發現用遞推的思想解這道題，可以找到一般的遞推關系，并可以利用這種遞推關系解決更為復雜的一些問題。

5.遞推法

我們先把文中題目所涉及的問題換一種說法。即把1，2，3，4四個數字排成一排，使得I不能排在第I位，I=1，2，3，4。求符合條件的排列數。

我們再把這問題推廣為一般的模式。把1，2，3，…，n這n個數字排成一排，使得I不能排在第I 位，I=1，2，3，…，n。求符合條件的排列數。

設n個數字的這種排列數為Dn，若能推出Dn的通項公式或遞推公式，那么上面的問題就迎刃而解且能解決一些較為復雜的問題。利用遞推的數學思想分析如下：

容易知道D1=0，D2=1，n≥3時，考慮1，2，3，…n這n個數字的所有符合條件的排列數（以下稱為n個元素的錯位排列數）。我們根據在排列中的第一位的數字是2，3，…，n，而將這些排列分成n-1類，顯然每一類的排列數相等。令dn表示第一位是2的排列數。那么有 Dn=（n-1）dn （1）

考察在dn中的排列，它們都是2I2 I3… In的形式，其中Ij≠j，j=2，3，…，n.我們進一步把這些排列分成兩類，稱I2=1的為第一子類，并把其中的排列個數記為dnˊ；稱I2≠1的為第二子類，它的排列個數記為dn〞，那么有 dn= dnˊ+ dn〞 （2）

在第一子類中的排列具有21 I3I4… In的形式，Ij≠j，j=3，4，…，n。所以dnˊ就是3，4，…，n，這n-2個元素的錯位排列數Dn-2。在第二子類中的排列具有2I2 I3… In的形式，其中I2≠1，Ij≠j，j=3，4，…，n。所以dn〞就是1，3，4，…，n，這n-1個元素的錯位排列數Dn-1。因此得到 dn = Dn-2 +Dn-1 （3）

把（3）代入（1）得Dn=（n-1）（Dn-2 +Dn-1）

于是我們得到遞推公式 （4）

Dn=（n-1）（Dn-2 +Dn-1）

D1=0，D2=1

解法五：利用遞推公式（4），我們有

D3=（3-1）（D1 +D2）=2×（0+1）=2，

D4=（4-1）（D2 +D3）=3×（1+2）=9，

故有9種方法。

顯然，與前述數種方法相比，遞推法更具有一般性，利用遞推公式（4），我們還可以較易地解決一些中學里常見的排列組合題。

例1.設有編號為1，2，3，4，5，6的六個球和編號為1，2，3，4，5，6的六個盒子，現將這六個球放入這六個盒內，要求每個盒子內投放一個球，并且恰好有兩個球的編號與盒子編號相同，試求這樣投放方法的種數。

解：從編號為1，2，3，4，5，6的六個球中任選兩個的方法數為C62。我們把選出的兩個球放在與它編號相同的盒子里，剩下的四個球的投放方法滿足遞推公式（4）的條件。所求的投放方法數為

C62×D4=15×9=135（種）。

例2.八人坐成一排，現要調換五個人的位置，其余三個人位置不動，共有（ ）種調換方法。

解：五個人調換位置，即五個人都不坐在原來的位置上。所以任意五個人調換位置的方法數D5滿足遞推公式（4）的條件。

由例1知D5=44。

∴共有C85×D5=56×44=2464（種）

另一方面，掌握遞推的數學思想對解某些其它應用性問題也是很有幫助的。例如下面的問題用遞推的思想來解答將很明了。

綜觀上述，可見運用遞推法求解某些排列組合應用題，思路明了，并可以找到一般的遞推關系用于解決同類問題，有助于培養邏輯思維能力。