由一道高考試題談全錯位排列問題

摘 要：錯位排列問題是排列組合問題中常見類型之一，解決方法常運用容斥原理但這個方法對大多數中學生來說相對陌生，不符合中學階段常規思維.本文從中學課堂常規思路出發，步步探究，給出全錯位排列問題的一套完整解決方案，以期對開拓學生數學思維有所幫助.

關鍵詞：賀卡問題；全錯位排列；遞推公式；通項公式

作者簡介：王常慶（1972-），男，山東鄆城人，本科，中學高級教師，研究方向：中學數學教學.

一、問題的提出

題目 同室4人各寫一張賀卡，然后收集起來，每人再從中各抽一張，但不能抽取自己寫的那一張，問共有幾種不同的抽法？

象這種“每個元素都不在限定的位置上”的排列問題，通常叫做全錯位排列問題.全錯位排列作為排列組合中的一類典型題目，難度較高. 筆者從常規思路出發，整理出一套完整的解決方案，現把研究過程及每一階段的成果展示出來，供大家參考.

二、問題的解決

法一（頂針法） 假設A、B、C、D四人所寫的賀卡分別為a、b、c、d，若先由A抽，共有3種抽法（b、c、d），若抽到b，則接下來由B抽，也有3種抽法（a、c、d），最后由C、D二人抽，均只有1種抽法，故由分步計數原理知共有3×3×1×1=9種抽法.

法二（列表法/枚舉法） 把A、B、C、D四人依次抽到的賀卡情況具體列表如下，共有9種方案，如表1：

法三（樹圖法） 為防止發生重復或遺漏，可分步畫圖，如圖1：

三、問題的探究

為方便探究，先對這類全錯位排列問題進行定義.

設n個編號為1，2，3，…，i，…，j，…，n的不同元素a1，a2，a3，…，ai，…，aj，…，an排成一列，且每個元素均不排在與其編號相同的位置，這樣的排列稱為全錯位排列，排列數記為Tn.

探究1 嘗試變更元素個數n，依上述解決方法，易得T1=0，T2=1，T3=2.

探究2 變更元素個數為5時，其全錯位排列數T5的求法如下：

（1）頂針法：若先由A抽，共有4種抽法；若抽到b，再由B抽，B抽到a與抽不到a，直接影響其他人的抽法，故而分為兩類：

①若B抽到a，其余3人再抽取相當于一個獨立 “3人組”，共有2種抽法；

②若B抽不到a，則B有3種抽法（c、d、e），設B抽到c，接下來由C抽，也有3種抽法，共有3×3=9種抽法.故題目最終結論為4×（2+3×3）=44種抽法.

（2）列表法、樹圖法均可解決，但工程龐大，不易操作.

探究3 由以上探究過程可知，當元素個數變更為5個時，其全錯位排列數的求解已是不易，若是元素個數變更為6個、7個甚至更多時，又該如何計算呢？下面仍先以“4人賀卡問題”為例解析如下：

先不考慮4張賀卡的具體歸屬，由4人隨意抽取，共有A44=24種抽法.其中包括以下不合題意的情況：

（1）4人中恰有1人取到自己寫的賀卡（以下簡稱自?。?，其余3人再抽取，相當于一個獨立的“3人組”，所以共有C14T3=4×2=8種抽法；

（2）4人中恰有2人自取，其余2人再抽，相當于一個獨立的“2人組”，共有C24T2=6×1=6種抽法；

（3）4人全部自取，共有1種抽法（不可能出現恰有3人自取情況）.

故“4人組”賀卡的抽法共有T4 =A44-2×C14-1×C24-1=9種.

下面可用同樣的方法完成T5的求解：

T5=A55-C15T4-C25T3-C35T2-1=44種.

小結 按上述解法，只要知道了T1，T2，T3，…的結果，依次遞推下去，便可求出任意n個元素的全錯位排列數Tn （n∈N*）. 當然，隨著人數n的增加，分類越來越多，計算量也越來越大.

探究4 為進一步尋求規律、簡化計算，筆者受到“斐波那契數列”的啟發，把已求得的幾個全錯位排數Tn及相應元素個數n（n∈N*）列表如下（表2）

由這兩個遞推公式，易得到T6=265及T7=1854，將Tn的計算向前推進了一大步.

探究5 上述遞推公式是通過不完全歸納法得到的，其正確性有待于證實.下面嘗試利用計數原理、數學歸納法的有關知識進行證明.

1遞推公式1的證明（利用計數原理）

首先易得T1=0，T2=1.

當n≥2時，總數為n+1個元素的全錯位排列可分兩步進行：

第一步，先從n+1個不同元素中任取一個元素ai，因其不能排在與其編號相對應的i 位，必排在剩下n 個位置之一，所以ai有n 種排法；

第二步，針對ai每一種排法，如果ai排在 j位，原對應j位的元素aj的排位又有兩種情況：

第1種情況，若aj恰好排在i位上，如表3

此時，除ai外的其他n個元素（包括aj）均有一個不能排的位置（aj不排在i位上），問題就轉化為其余這n個元素全錯位排列，排列數為Tn.

故綜合上述步驟，由乘法原理和加法原理可得：Tn+1=n （Tn-1+Tn） （n≥2， n∈N*）.

2遞推公式2的證明（利用數學歸納法）

首先，易得T1=0，T2=1，顯然當n=2時，Tn=n Tn-1+（-1）n 成立；

其次，假設當n=k時（k≥2， k∈N*），Tn=n Tn-1+（-1）n 成立，即Tk=k Tk-1+（-1）k.

從而k Tk-1 =Tk -（-1）k=Tk+（-1）k+1.

又由遞推公式1可得Tk+1=k （Tk-1+Tk）.

從而Tk+1=kTk-1+kTk=Tk+（-1）k+1+kTk=（k+1 ）Tk+（-1）k+1.即Tk+1=（k+1 ）T（k+1）-1+（-1）k+1.故當n=k+1時，Tn=n Tn-1+（-1）n亦成立.

綜合上述步驟可知，Tn=n Tn-1+（-1）n對于任意自然數n（n≥2， n∈N*）均成立.

探究6 上述公式雖已獲得證明，但畢竟只是遞推公式，如果能夠利用構造數列的思想，導出{Tn}的通項公式，方才圓滿.

解析 將Tn=n Tn-1+（-1）n的兩邊同時除以n！ 得

Tn n！ = nTn-1 n！ + （-1）nn！ = Tn -1 （n-1）！ + （-1）nn！.

從而有Tnn！-Tn-1（n-1）！=（-1）nn！.

于是，T22！-T11！=（-1）22！，T33！-T22！=（-1）33！，…，Tnn！-Tn-1（n-1）！=（-1）nn！.

將這n-1個等式累加得Tnn！-T11！=∑ni=2（-1）ii！.

又T1=0，故有Tnn！=∑ni=2（-1）ii！.

從而有Tn=n！∑ni=2（-1）ni?。╪≥2， n∈N*）.

在解決排列組合問題時，經常涉及到全錯位或部分錯位的排列問題，在元素不是很多時，我們可以用枚舉或樹枝圖的方法，也可利用排除的方法對問題進行討論；但當元素較多時可嘗試尋求排列數的遞推公式或通項公式，以期對解決這一類問題提供方便.

參考文獻：

[1]李宇襄組合數學[M].北京：北京師范大學出版社，2012.

[2]龔兵全錯位排列[J].中學生數學，2011（17）：26

[3]程孝剛對錯位排列問題的探究[J]高中數學教與學，2009（08）：42-43.