吳如光

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

一、錯(cuò)排問(wèn)題

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

二、容斥原理解釋

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

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

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

三、按分步計(jì)數(shù)原理解釋

第1步：將1號(hào)信錯(cuò)放，有n-1種放法，不妨假設(shè)放在2號(hào)信封里；

第2步：將2號(hào)信錯(cuò)放，有兩類放法：

①：2號(hào)信放入1號(hào)信封里，則其余n-2封信與信封將錯(cuò)放，有Dn-2種放法.

②：若2號(hào)信不放在1號(hào)信封里，此時(shí)相當(dāng)于n-1封信(除1號(hào)信)放入n-1個(gè)信封(除2號(hào)信封)，每封信都有一個(gè)禁止放的信封，因此有Dn-1種放法.

由此可得遞推關(guān)系：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),

四、按分類計(jì)數(shù)原理解釋

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

由引理可得：

以上對(duì)錯(cuò)排問(wèn)題的幾種不同看法，得到了不同的遞推關(guān)系，但是殊途同歸，加深了對(duì)錯(cuò)排問(wèn)題的理解，其結(jié)論的形式優(yōu)美，讓我們?cè)俅胃惺艿綌?shù)學(xué)的美妙.