解決“錯(cuò)位排列”問題的一般方法

張仁海

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

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

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

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

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

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

第一步，填數(shù)字1在2和3號(hào)位中任選一個(gè)位置將數(shù)字1填入，有2種填法.不妨將其填入2號(hào)位.

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

① 若將數(shù)字2填入1號(hào)位，則只需將數(shù)字3錯(cuò)位填入3號(hào)位上，有c1種填法；

② 若不將數(shù)字2填入1號(hào)位，則須將數(shù)字2和3填入1號(hào)和3號(hào)位，這等價(jià)于將數(shù)字2和3錯(cuò)位填入2號(hào)和3號(hào)位（因?yàn)閿?shù)字2不能填入1號(hào)位，也不能填入2號(hào)位），有c2種填法.由分類計(jì)數(shù)原理可知，填數(shù)字2有（c1+c2）種填法.最后，由分步計(jì)數(shù)原理得，c3=2（c2+c1）=2×（0+1）=2.

我們?cè)賮碛?jì)算c4.仍需分兩步完成：

第一步，填數(shù)字1.在2、3、4號(hào)位中任選一個(gè)位置將數(shù)字1填入，有3種填法.不妨將其填入2號(hào)位.

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

① 若將數(shù)字2填入1號(hào)位，則只需將數(shù)字3和4錯(cuò)位填入3號(hào)和4號(hào)位上，有c2種填法；

② 若不將數(shù)字2填入1號(hào)位，則須將數(shù)字2，3，4填入1號(hào)，3號(hào)，4號(hào)位，這等價(jià)于將數(shù)字2，3，4錯(cuò)位填入2號(hào)，3號(hào)，4號(hào)位（因?yàn)閿?shù)字2不能填入1號(hào)位，也不能填入2號(hào)位），有c3種填法.由分類計(jì)數(shù)原理可知，填數(shù)字2有（c2+c3）種填法.

最后，由分步計(jì)數(shù)原理得，

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）個(gè)正整數(shù)1，2，3，…，n錯(cuò)位填入編號(hào)為1，2，3，…，n的n個(gè)空位，需分兩步完成：

第一步，填數(shù)字1，在2～n號(hào)位中任選一個(gè)k號(hào)位，將數(shù)字1填入，有n-1種填法.

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

①若將數(shù)字k填入1號(hào)位，則只需將數(shù)字2，3，…，k-1，k+1，…，n這n-2個(gè)正整數(shù)錯(cuò)位填入2，3，…，k-1，k+1，…，n有cn-2種填法；

②若不將數(shù)字k填入1號(hào)位，則須將數(shù)字2，3，…，k，…，n這n-1個(gè)正整數(shù)錯(cuò)位填入序號(hào)為1，2，3，…，k-1，k+1，…，n這n-1個(gè)空位，這等價(jià)于將數(shù)字2，3，…，k，…，n這n-1個(gè)正整數(shù)錯(cuò)位填入序號(hào)為2，3，…，k，…，n這n-1個(gè)空位中（因?yàn)閿?shù)字k不能填入1號(hào)位，也不能填入k號(hào)位），有cn-1種填法.由分類計(jì)數(shù)原理可知，填數(shù)字k有cn-1+cn-2種填法.

最后，由分步計(jì)數(shù)原理得，

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

因此，錯(cuò)位排列數(shù)的一個(gè)遞推公式為：

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

由此遞推公式可知，錯(cuò)位排列數(shù)構(gòu)成數(shù)列：

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

其排列規(guī)律是，從第3項(xiàng)起，以后的每一項(xiàng)都等于它前面兩項(xiàng)和的項(xiàng)數(shù)減1倍.

一般情況下，在高中階段，只要記住這個(gè)數(shù)列的前5項(xiàng)就足夠了.

例1編號(hào)為1，2，3，4，5的五個(gè)人，分別坐在座號(hào)為1，2，3，4，5的座位上：

（1）沒有一人號(hào)碼一致的坐法有多少種？

（2）恰有兩人號(hào)碼一致的坐法有多少種？

（3）至多有兩人號(hào)碼一致的坐法有多少種？

解由錯(cuò)位排列數(shù)的遞推公式知：

（1）沒有一人號(hào)碼一致的坐法有c5=44種.

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

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

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

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

由分類計(jì)數(shù)原理得，至多有兩人號(hào)碼一致的坐法有：44+45+20=109種.

例2某地進(jìn)行換屆選舉，要從甲、乙、丙、丁4人中選出3人擔(dān)任3種不同的職務(wù)，規(guī)定上界任職的甲、乙、丙3人不能連任原職，則不同的任職結(jié)果有種.

解分兩類：

① 不含?。阂?yàn)榧?、乙、丙不能任原職，這相當(dāng)于3個(gè)元素的錯(cuò)位排列，所以有c3=2種；

② 含?。阂?yàn)榧?、乙、丙不能任原職，故必有一人排空（無職位），而丁又不能排空（有職位），這相當(dāng)于4個(gè)元素的錯(cuò)位排列，所以有c4=9種.

由分類計(jì)數(shù)原理，共有2+9=11（種）.

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

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

（2）設(shè)X為該參賽者此題的得分，求X的分布列與數(shù)學(xué)期望.

解（1）該參賽者恰好連對(duì)一條，有C14種可能，其他3條沒連對(duì)，這相當(dāng)于三個(gè)數(shù)的錯(cuò)位排列，有c3種可能，故有C14c3=4×2=8種不同的排法，而該參賽者連線的所有可能情況有A44=24種，故該參賽者恰好連對(duì)一條的概率為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的數(shù)學(xué)期望為E（X）=（-8）×924+（-1）×824+6×624+20×124=-1.