由一道高考試題談全錯(cuò)位排列問(wèn)題

摘 要：錯(cuò)位排列問(wèn)題是排列組合問(wèn)題中常見(jiàn)類型之一，解決方法常運(yùn)用容斥原理但這個(gè)方法對(duì)大多數(shù)中學(xué)生來(lái)說(shuō)相對(duì)陌生，不符合中學(xué)階段常規(guī)思維.本文從中學(xué)課堂常規(guī)思路出發(fā)，步步探究，給出全錯(cuò)位排列問(wèn)題的一套完整解決方案，以期對(duì)開(kāi)拓學(xué)生數(shù)學(xué)思維有所幫助.

關(guān)鍵詞：賀卡問(wèn)題；全錯(cuò)位排列；遞推公式；通項(xiàng)公式

作者簡(jiǎn)介：王常慶（1972-），男，山東鄆城人，本科，中學(xué)高級(jí)教師，研究方向：中學(xué)數(shù)學(xué)教學(xué).

一、問(wèn)題的提出

題目 同室4人各寫(xiě)一張賀卡，然后收集起來(lái)，每人再?gòu)闹懈鞒橐粡垼荒艹槿∽约簩?xiě)的那一張，問(wèn)共有幾種不同的抽法？

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

二、問(wèn)題的解決

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

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

法三（樹(shù)圖法） 為防止發(fā)生重復(fù)或遺漏，可分步畫(huà)圖，如圖1：

三、問(wèn)題的探究

為方便探究，先對(duì)這類全錯(cuò)位排列問(wèn)題進(jìn)行定義.

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

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

探究2 變更元素個(gè)數(shù)為5時(shí)，其全錯(cuò)位排列數(shù)T5的求法如下：

（1）頂針?lè)ǎ喝粝扔葾抽，共有4種抽法；若抽到b，再由B抽，B抽到a與抽不到a，直接影響其他人的抽法，故而分為兩類：

①若B抽到a，其余3人再抽取相當(dāng)于一個(gè)獨(dú)立 “3人組”，共有2種抽法；

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

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

探究3 由以上探究過(guò)程可知，當(dāng)元素個(gè)數(shù)變更為5個(gè)時(shí)，其全錯(cuò)位排列數(shù)的求解已是不易，若是元素個(gè)數(shù)變更為6個(gè)、7個(gè)甚至更多時(shí)，又該如何計(jì)算呢？下面仍先以“4人賀卡問(wèn)題”為例解析如下：

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

（1）4人中恰有1人取到自己寫(xiě)的賀卡（以下簡(jiǎn)稱自取），其余3人再抽取，相當(dāng)于一個(gè)獨(dú)立的“3人組”，所以共有C14T3=4×2=8種抽法；

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

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

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

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

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

小結(jié) 按上述解法，只要知道了T1，T2，T3，…的結(jié)果，依次遞推下去，便可求出任意n個(gè)元素的全錯(cuò)位排列數(shù)Tn （n∈N*）. 當(dāng)然，隨著人數(shù)n的增加，分類越來(lái)越多，計(jì)算量也越來(lái)越大.

探究4 為進(jìn)一步尋求規(guī)律、簡(jiǎn)化計(jì)算，筆者受到“斐波那契數(shù)列”的啟發(fā)，把已求得的幾個(gè)全錯(cuò)位排數(shù)Tn及相應(yīng)元素個(gè)數(shù)n（n∈N*）列表如下（表2）

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

探究5 上述遞推公式是通過(guò)不完全歸納法得到的，其正確性有待于證實(shí).下面嘗試?yán)糜?jì)數(shù)原理、數(shù)學(xué)歸納法的有關(guān)知識(shí)進(jìn)行證明.

1遞推公式1的證明（利用計(jì)數(shù)原理）

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

當(dāng)n≥2時(shí)，總數(shù)為n+1個(gè)元素的全錯(cuò)位排列可分兩步進(jìn)行：

第一步，先從n+1個(gè)不同元素中任取一個(gè)元素ai，因其不能排在與其編號(hào)相對(duì)應(yīng)的i 位，必排在剩下n 個(gè)位置之一，所以ai有n 種排法；

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

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

此時(shí)，除ai外的其他n個(gè)元素（包括aj）均有一個(gè)不能排的位置（aj不排在i位上），問(wèn)題就轉(zhuǎn)化為其余這n個(gè)元素全錯(cuò)位排列，排列數(shù)為Tn.

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

2遞推公式2的證明（利用數(shù)學(xué)歸納法）

首先，易得T1=0，T2=1，顯然當(dāng)n=2時(shí)，Tn=n Tn-1+（-1）n 成立；

其次，假設(shè)當(dāng)n=k時(shí)（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.故當(dāng)n=k+1時(shí)，Tn=n Tn-1+（-1）n亦成立.

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

探究6 上述公式雖已獲得證明，但畢竟只是遞推公式，如果能夠利用構(gòu)造數(shù)列的思想，導(dǎo)出{Tn}的通項(xiàng)公式，方才圓滿.

解析 將Tn=n Tn-1+（-1）n的兩邊同時(shí)除以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個(gè)等式累加得Tnn！-T11！=∑ni=2（-1）ii！.

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

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

在解決排列組合問(wèn)題時(shí)，經(jīng)常涉及到全錯(cuò)位或部分錯(cuò)位的排列問(wèn)題，在元素不是很多時(shí)，我們可以用枚舉或樹(shù)枝圖的方法，也可利用排除的方法對(duì)問(wèn)題進(jìn)行討論；但當(dāng)元素較多時(shí)可嘗試尋求排列數(shù)的遞推公式或通項(xiàng)公式，以期對(duì)解決這一類問(wèn)題提供方便.

參考文獻(xiàn)：

[1]李宇襄組合數(shù)學(xué)[M].北京：北京師范大學(xué)出版社，2012.

[2]龔兵全錯(cuò)位排列[J].中學(xué)生數(shù)學(xué)，2011（17）：26

[3]程孝剛對(duì)錯(cuò)位排列問(wèn)題的探究[J]高中數(shù)學(xué)教與學(xué)，2009（08）：42-43.