錯排問題的模型解釋及求解

吳如光

(江蘇省南京航空航天大學附屬高級中學 210000)

一、錯排問題

錯排問題，又稱更列問題，是組合數學中的經典問題之一.該問題有許多具體的形式，例如：①在寫信時將n封信裝到n個不同的信封里，有多少種全部裝錯信封的情況？②n個人各寫一張賀卡相互贈送，有多少種贈送方法？從中概括出其數學模型：一個有n個元素的排列，若這個排列中所有的元素都不在自己原來的位置上，那么這樣的排列就稱為原排列的一個錯排，n個元素的錯排數記為Dn，求Dn的通項公式.

二、容斥原理解釋

容斥原理：設A1,A2，…，An為有限集合，用|Ai|表示集合Ai中的元素個數，則有：

以裝信封為例：記第i封信裝對的事件為Ai(i=1,2…,n).

不難得出：|Ai|=(n-1)!,|Ai∩Aj|=(n-2)!,…,|A1∩A2∩…An|=1.

三、按分步計數原理解釋

第1步：將1號信錯放，有n-1種放法，不妨假設放在2號信封里；

第2步：將2號信錯放，有兩類放法：

①：2號信放入1號信封里，則其余n-2封信與信封將錯放，有Dn-2種放法.

②：若2號信不放在1號信封里，此時相當于n-1封信(除1號信)放入n-1個信封(除2號信封)，每封信都有一個禁止放的信封，因此有Dn-1種放法.

由此可得遞推關系：D1=0,D2=1,Dn=(n-1)·(Dn-1+Dn-2),n≥3.

∴Dn-n·Dn-1=-[Dn-1-(n-1)·Dn-2]，

∴Dn-n·Dn-1=(-1)n,(n≥2),

四、按分類計數原理解釋

只需令引理中的an=n!，bn=Dn.

由引理可得：

以上對錯排問題的幾種不同看法，得到了不同的遞推關系，但是殊途同歸，加深了對錯排問題的理解，其結論的形式優美，讓我們再次感受到數學的美妙.