解決“錯位排列”問題的一般方法

張仁海

問題同室四人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送來的賀年卡，則四張賀年卡不同的分配方式有（）.

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

這個問題等價于：將1，2，3，4這四個正整數分別填入編號為1，2，3，4的四個空位，且每個空位上所填數字與其序號均不相同，問有多少種不同的填法？我們稱這樣的排列為錯位排列.這是一個很復雜的排列問題.下面，我們就來研究解決這類問題的一般方法.

我們把這類問題推廣到一般情形：

將n個正整數1，2，3，…，n分別填入編號為1，2，3，…，n的n個空位，且每個空位上所填數字與其序號均不相同，并把所有這樣排列的個數記為cn（借助“錯”字拼音的首字母）.

顯然，c1=0，c2=1.下面，我們來計算c3.需分兩步完成：

第一步，填數字1在2和3號位中任選一個位置將數字1填入，有2種填法.不妨將其填入2號位.

第二步，填數字2.又分兩類來完成：

① 若將數字2填入1號位，則只需將數字3錯位填入3號位上，有c1種填法；

② 若不將數字2填入1號位，則須將數字2和3填入1號和3號位，這等價于將數字2和3錯位填入2號和3號位（因為數字2不能填入1號位，也不能填入2號位），有c2種填法.由分類計數原理可知，填數字2有（c1+c2）種填法.最后，由分步計數原理得，c3=2（c2+c1）=2×（0+1）=2.

我們再來計算c4.仍需分兩步完成：

第一步，填數字1.在2、3、4號位中任選一個位置將數字1填入，有3種填法.不妨將其填入2號位.

第二步，填數字2，又分兩類來完成：

① 若將數字2填入1號位，則只需將數字3和4錯位填入3號和4號位上，有c2種填法；

② 若不將數字2填入1號位，則須將數字2，3，4填入1號，3號，4號位，這等價于將數字2，3，4錯位填入2號，3號，4號位（因為數字2不能填入1號位，也不能填入2號位），有c3種填法.由分類計數原理可知，填數字2有（c2+c3）種填法.

最后，由分步計數原理得，

c4=3（c3+c2）=3×（2+1）=9.

這就是開頭的那道高考題的解，故此題選B.

同理可得：c5=4（c4+c3）=4×（2+9）=44.

觀察：c3=2（c2+c1），c4=3（c3+c2），c5=4（c4+c3），….

猜想：cn=（n-1）（cn-1+cn-2）（n≥3）.

證明將n（n≥3）個正整數1，2，3，…，n錯位填入編號為1，2，3，…，n的n個空位，需分兩步完成：

第一步，填數字1，在2～n號位中任選一個k號位，將數字1填入，有n-1種填法.

第二步，填數字k，又分兩類來完成：

①若將數字k填入1號位，則只需將數字2，3，…，k-1，k+1，…，n這n-2個正整數錯位填入2，3，…，k-1，k+1，…，n有cn-2種填法；

②若不將數字k填入1號位，則須將數字2，3，…，k，…，n這n-1個正整數錯位填入序號為1，2，3，…，k-1，k+1，…，n這n-1個空位，這等價于將數字2，3，…，k，…，n這n-1個正整數錯位填入序號為2，3，…，k，…，n這n-1個空位中（因為數字k不能填入1號位，也不能填入k號位），有cn-1種填法.由分類計數原理可知，填數字k有cn-1+cn-2種填法.

最后，由分步計數原理得，

cn=（n-1）（cn-1+cn-2）（n≥3）.

因此，錯位排列數的一個遞推公式為：

c1=0，c2=1，cn=（n-1）（cn-1+cn-2）（n∈N*，n≥3）.

由此遞推公式可知，錯位排列數構成數列：

0，1，2，9，44，265，1 854，…，（n-1）（cn-1+cn-2），….

其排列規律是，從第3項起，以后的每一項都等于它前面兩項和的項數減1倍.

一般情況下，在高中階段，只要記住這個數列的前5項就足夠了.

例1編號為1，2，3，4，5的五個人，分別坐在座號為1，2，3，4，5的座位上：

（1）沒有一人號碼一致的坐法有多少種？

（2）恰有兩人號碼一致的坐法有多少種？

（3）至多有兩人號碼一致的坐法有多少種？

解由錯位排列數的遞推公式知：

（1）沒有一人號碼一致的坐法有c5=44種.

（2）恰有兩人號碼一致的坐法有C25c3=10×2=20（種）.

（3）分三類：① 沒有一人號碼一致的坐法有c5=44種；

② 恰有一人號碼一致的坐法有C15c4=5×9=45（種）；

③ 恰有兩人號碼一致的坐法有C25c3=10×2=20（種）.

由分類計數原理得，至多有兩人號碼一致的坐法有：44+45+20=109種.

例2某地進行換屆選舉，要從甲、乙、丙、丁4人中選出3人擔任3種不同的職務，規定上界任職的甲、乙、丙3人不能連任原職，則不同的任職結果有種.

解分兩類：

① 不含丁：因為甲、乙、丙不能任原職，這相當于3個元素的錯位排列，所以有c3=2種；

② 含丁：因為甲、乙、丙不能任原職，故必有一人排空（無職位），而丁又不能排空（有職位），這相當于4個元素的錯位排列，所以有c4=9種.

由分類計數原理，共有2+9=11（種）.

例3為了迎接青奧會的召開，某校舉行了一次體育知識競賽，其中一道題是連線題，要求將4種不同的消防工具與它們的4種不同的用途一對一連線.規定：每連對一條得5分，連錯一條得-2分.某參賽者隨機用4條線把消防工具與用途一對一全部連接起來.

（1）求該參賽者恰好連對一條的概率；

（2）設X為該參賽者此題的得分，求X的分布列與數學期望.

解（1）該參賽者恰好連對一條，有C14種可能，其他3條沒連對，這相當于三個數的錯位排列，有c3種可能，故有C14c3=4×2=8種不同的排法，而該參賽者連線的所有可能情況有A44=24種，故該參賽者恰好連對一條的概率為P=C14c3A44=824=13.

（2）X的所有可能取值為-8，-1，6，20.

P（X=-8）=c4A44=924，P（X=-1）=C14c3A44=4×224=824，

P（X=6）=C24c2A44=6×124=624，P（X=20）=1A44=124.

∴X的分布列為

X-8-1620

P924824624

124

∴X的數學期望為E（X）=（-8）×924+（-1）×824+6×624+20×124=-1.