錯位排列和禁位排列及其排列數公式

【摘要】分析錯位排列和禁位排列的特征、區別和聯系，給出相應的排列數計算公式.

【關鍵詞】錯位排列；禁位排列；全錯位排列；容斥原理

錯位排列和禁位排列是學生容易混淆，解題常感棘手的排列難題，有必要對這兩個概念加以區分，并對其計算方法進行探討.

錯位排列:n個相異元素中m(≤n)個元素ai1，ai2，…，aim，其中aik(k=1，2，…，m)不在第ik(k=1，2，…，m)個位置(以下簡稱其為aik的本位)，而其他n-m個元素中的任何一個都在原來的位置(本位)的排列.

禁位排列(本文只討論一個元素禁止排在一個位置的情況):n個相異元素中的m個元素ai1，ai2，…，aim，其中aik(k=1，2，…，m)不能排在第jk(k=1，2，…，m)個位置的排列.

兩者的區別在于：錯位排列中除這m個元素之外的其他n-m個元素都在本位，即這m個元素只能在m個位置i1，i2，…，im中排列，且不出現aik(k=1，2，…，m)在ik位的情況；而禁位排列中只限制m個元素不在本位，因此aik(k=1，2，…，m)可以排在1，2，…，n中除ik之外的任何位置.

求禁位排列數，只需從n個元素的全排列中除去指定元素占本位的排列即可，其中有1個元素占本位的排列數是C1mPn-1n-1，有2個元素占本位的排列數是C2mPn-2n-2，…，n個元素都占本位的排列是CmmPn-mn-m.

記錯位排列和禁位排列的排列數分別為Dmn，Emn，并規定P00=C00=0!=1，則由容斥原理(把多減的補回，多補的再減去)，有

公式一 Emn=n!C0m-(n-1)!C1m+(n-2)!C2m-…+(-1)m(n-m)!Cmm.

證明 易知當m=0時，等式成立.

假設Ekn=∑ki=0(-1)iCikPn-in-i.

那么，當m=k+1時，設第k+1個元素為a，則前k個元素不占本位而a占本位的排列數為

Ekn-1=∑ki=0(-1)iCikPn-i-1n-i-1.

因而前k+1個元素不占本位的全排列即為從前k個元素不占本位的全部排列中再除去a占本位的排列，即

Ek+1n=Ekn-Ekn-1

=∑ki=0(-1)iCikPn-in-i-∑ki=0(-1)iCikPn-i-1n-i-1

=C0kPnn+∑ki=1(-1)i(Cik+Ci-1k)Pn-in-i+

(-1)k+1CkkPn-k-1n-k-1

=∑k+1i=0(-1)iCik+1Pn-in-i.

由上可知公式一成立.證畢.

錯位排列有兩種情況：1.限定的m個元素不占本位；2.未限定的m個元素不占本位.

特別地，當n個元素都不在本位時，稱為全錯位排列.記其排列數為Dn，則有

公式二 Dn=n!C0n-(n-1)!C1n+(n-2)!C2n-…+(-1)n(n-1)!Cmn.或

公式二(*)

Dn=n!1-11!+12!-13!+…+(-1)n-11n!.

由公式二，n個相異元素中m個指定元素的錯位排列數為：

公式三 Dm=m!C0m-(m-1)!C1m+(m-2)!C2m-…+(-1)mCmm.

n個相異元素中有m個元素的錯位排列數為：

公式四 Dmn=CmnDm.

易知，當n=m時，公式一、公式三、公式四都可表示為公式二.

例1 要安排6名學生分別擔任6個班干部工作，其中甲不能當班長，乙不能當體育委員，丙不能當生活委員，共有多少種安排方法？(E36)

例2 甲、乙、丙、丁四人排成一排，甲不能站一位，乙不能站二位，丙不能站三位，丁不能站四位，共有多少種排法？(D4)

例3 一個人寫了8封不同的信及相應的8個不同的信封，問：將這8封信裝進信封時(每個信封中只能裝一封信)，有3封信裝錯的裝法有多少種？(D38)

【參考文獻】

盧開澄，盧華明.組合數學(第三版)［M］.北京：清華大學出版社，2002.