容斥原理在更列問(wèn)題中的應(yīng)用實(shí)例

【摘要】容斥原理是中學(xué)數(shù)學(xué)中的重要定理，在計(jì)數(shù)時(shí)先不考慮重疊的情況，把包含于某內(nèi)容中的所有對(duì)象的數(shù)目先計(jì)算出來(lái)，然后再把計(jì)算時(shí)重復(fù)計(jì)算的數(shù)目排斥出去，使得計(jì)算的結(jié)果既無(wú)遺漏又無(wú)重復(fù).而更列問(wèn)題則是組合數(shù)學(xué)的難點(diǎn)之一.本文首先給出容斥原理的定義及性質(zhì)與證明，然后引出更列問(wèn)題，同時(shí)給出更列問(wèn)題的一個(gè)有效解法，最后討論容斥原理在更列問(wèn)題中的一系列應(yīng)用.

【關(guān)鍵詞】容斥原理；更列問(wèn)題；排列

一、容斥原理的概念

在計(jì)數(shù)時(shí)，必須注意無(wú)一重復(fù)，無(wú)一遺漏.為了使重疊部分不被重復(fù)計(jì)算，人們?cè)谟?jì)數(shù)時(shí)，必須注意研究出一種新的計(jì)算方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內(nèi)容中的所有對(duì)象的數(shù)目先計(jì)算出來(lái)，然后再把計(jì)算時(shí)重復(fù)計(jì)算的數(shù)目排斥出去，使得計(jì)算的結(jié)果既無(wú)遺漏又無(wú)重復(fù)，這種計(jì)數(shù)的方法稱之為容斥原理

二、容斥原理的性質(zhì)

假定|A|表示集合A的元素個(gè)數(shù)，根據(jù)加法原則，若A∪B=，則|A∪B|=|A|+|B|.若A∩B=?xí)r，這時(shí)將|A∪B|多計(jì)算一次，可以直觀有|A∪B|=|A|+|B|-|A∩B|.對(duì)于n個(gè)有限集合A1，A2，A3，…，An，同樣有定理：

|A1∪A2∪…∪An|=∑n-1i=1|Ai|-∑n-1i=1∑j>i|An-1∩An|+…+(-1)n-2|A1∩An|∪(A2∩An)∪…∪(An-1∩An)|+∑ni=1∑j>1∑k>1|Ai∩Aj∩Ak|+…+(-1)n-1|A1∩A2∩…∩An|.

三、更列問(wèn)題的概念

什么叫作更列問(wèn)題？我們先來(lái)看一個(gè)題目，現(xiàn)有五件球衣分屬五個(gè)運(yùn)動(dòng)員，現(xiàn)問(wèn)五個(gè)運(yùn)動(dòng)員都不穿自己的球衣，而穿其他球員的球衣，這樣的穿法有幾種?這就是5個(gè)元素的更列問(wèn)題.

就一般而言，有幾個(gè)不同的元素，它們一一對(duì)應(yīng)于幾個(gè)位置，如果這n個(gè)元素都不排在自身對(duì)應(yīng)的位置上，這種排列的方法稱為幾個(gè)元素的一個(gè)更列.現(xiàn)要計(jì)算這種更列的個(gè)數(shù).大數(shù)學(xué)家歐拉曾用容斥原理求出了n個(gè)元素的更列個(gè)數(shù)為:

Mn=n!1-11!+22!-33!+…+(-1)nn! .

四、容斥原理與更列問(wèn)題的關(guān)系

這是運(yùn)用組合數(shù)學(xué)的方法解決問(wèn)題的一個(gè)運(yùn)用.下面我們就證明一下這個(gè)公式.現(xiàn)在，我們來(lái)考慮整數(shù)1，2，…，n的排列.如果1不出現(xiàn)在第1個(gè)位置，2不出現(xiàn)在第2個(gè)位置，…，n不出現(xiàn)在第n個(gè)位置，這時(shí)，這些整數(shù)的一個(gè)排列說(shuō)成是它們的一個(gè)更列.也就是說(shuō)，沒(méi)有一個(gè)整數(shù)出現(xiàn)在它的自然位置上.用Mn記1，2，…，n這n個(gè)數(shù)的更列的個(gè)數(shù).如何來(lái)求這個(gè)Mn，這既是一個(gè)排列問(wèn)題，同時(shí)又是一個(gè)數(shù)列的通項(xiàng)問(wèn)題.

我們不妨先考慮這個(gè)數(shù)列的前幾項(xiàng).整數(shù)更列的個(gè)數(shù)可由解遞歸關(guān)系而得到.考慮整數(shù)1，2，…，n的更列，對(duì)其進(jìn)行合理分布，恰當(dāng)分類.

由分步計(jì)數(shù)原理和分類計(jì)數(shù)原理，我們便得到了數(shù)列{Mn}的遞推關(guān)系式:Mn=(n-1)(Mn-1+Mn-2).(*)

顯然，M1=0，M2=1，M3=2.(*)式可進(jìn)一步變形，Mn-nMn-1=-［Mn-1-(n-1)Mn-2］=…=(-1)n-3#8226;(M3-3M2)=(-1)n-2=(-1)n.

Mn-nMn-1=(-1)n式兩邊同乘1n!，則有

Mnn!-Mn-1(n-1)!=(-1)nn!.（1）

由累加法，得Mn=n!1-11!+22!-33!+…+(-1)nn! .

五、容斥原理在更列問(wèn)題中的應(yīng)用

例1 4只小鳥(niǎo)飛入四個(gè)不同的籠子里，每只小鳥(niǎo)都有自己的一個(gè)籠子(不同的鳥(niǎo)，籠子也不同)，每個(gè)籠子只能飛進(jìn)一只鳥(niǎo)，若都不飛進(jìn)自己的籠子，應(yīng)有多少種不同的飛法？

解 為了準(zhǔn)確地計(jì)算出有多少種不同的飛法，先求出4只小鳥(niǎo)隨意飛有多少種不同的飛法，然后減去不符合條件的飛法.

記A1={甲飛入自己的籠子而另3只鳥(niǎo)隨意飛的飛法}，A2={乙飛入自己的籠子而另3只鳥(niǎo)隨意飛的飛法}，A3={丙飛入自己的籠子而另3只鳥(niǎo)隨意飛的飛法}，A4={丁飛入自己的籠子而另3只鳥(niǎo)隨意飛的飛法}.

根據(jù)上面提到的公式：

Mn=n!-C1n(n-1)!+C1n(n-2)!-…+(-1)nCnn(n-n)!

=n!1-11!+22!-33!+…+(-1)nn!.

若是5只小鳥(niǎo)按題意飛入鳥(niǎo)籠，則有Mn=5!12!-13!+14!-15!=44（種）不同的飛法.

例2 某市有8個(gè)縣，每縣派出一個(gè)巡視組到本市別的縣去檢查工作（每縣去一組），問(wèn)巡視組有多少種不同的分派方法？

解 設(shè)這8個(gè)縣的編號(hào)為1，2，…，8，而ai為第i號(hào)縣（i=1，2，…，8）派出的巡視組.I表示這8個(gè)巡視組分派到這8個(gè)縣（每縣一組）的所有可能的方法組成的集合，Ai表示I中ai分到i號(hào)縣的分配方法組成的集合（i=1，2，…，8）.依題意，根據(jù)公式Mn=n!-C1n(n-1)!+C1n(n-2)!-…+(-1)n#8226;Cnn(n-n)!=8!-C18(8-1)!+C17(7-2)!-…+(-1)8#8226;C88(8-8)!=14833（種）分配方法，即為所求.

【參考文獻(xiàn)】

［1］李超英.排列和數(shù)列的匯合點(diǎn)——有趣的更列問(wèn)題.中學(xué)數(shù)學(xué)參考，2003（9）：35.

［2］周小華.由“小鳥(niǎo)飛錯(cuò)鳥(niǎo)籠”談容斥原理的應(yīng)用.紹興文理學(xué)院院報(bào)，2001（2）.

［3］吳國(guó)柱，郝端緒.容斥原理在組合數(shù)學(xué)中的若干應(yīng)用.冀東學(xué)刊，1994（6）：23.

［4］萬(wàn)大慶.關(guān)于容斥原理的一些注記［J］.四川大學(xué)學(xué)報(bào)（自然科學(xué)版），1985，22(1):15-19.