容斥原理在更列問題中的應用實例

【摘要】容斥原理是中學數學中的重要定理，在計數時先不考慮重疊的情況，把包含于某內容中的所有對象的數目先計算出來，然后再把計算時重復計算的數目排斥出去，使得計算的結果既無遺漏又無重復.而更列問題則是組合數學的難點之一.本文首先給出容斥原理的定義及性質與證明，然后引出更列問題，同時給出更列問題的一個有效解法，最后討論容斥原理在更列問題中的一系列應用.

【關鍵詞】容斥原理；更列問題；排列

一、容斥原理的概念

在計數時，必須注意無一重復，無一遺漏.為了使重疊部分不被重復計算，人們在計數時，必須注意研究出一種新的計算方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內容中的所有對象的數目先計算出來，然后再把計算時重復計算的數目排斥出去，使得計算的結果既無遺漏又無重復，這種計數的方法稱之為容斥原理

二、容斥原理的性質

假定|A|表示集合A的元素個數，根據加法原則，若A∪B=，則|A∪B|=|A|+|B|.若A∩B=時，這時將|A∪B|多計算一次，可以直觀有|A∪B|=|A|+|B|-|A∩B|.對于n個有限集合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|.

三、更列問題的概念

什么叫作更列問題？我們先來看一個題目，現有五件球衣分屬五個運動員，現問五個運動員都不穿自己的球衣，而穿其他球員的球衣，這樣的穿法有幾種?這就是5個元素的更列問題.

就一般而言，有幾個不同的元素，它們一一對應于幾個位置，如果這n個元素都不排在自身對應的位置上，這種排列的方法稱為幾個元素的一個更列.現要計算這種更列的個數.大數學家歐拉曾用容斥原理求出了n個元素的更列個數為:

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

四、容斥原理與更列問題的關系

這是運用組合數學的方法解決問題的一個運用.下面我們就證明一下這個公式.現在，我們來考慮整數1，2，…，n的排列.如果1不出現在第1個位置，2不出現在第2個位置，…，n不出現在第n個位置，這時，這些整數的一個排列說成是它們的一個更列.也就是說，沒有一個整數出現在它的自然位置上.用Mn記1，2，…，n這n個數的更列的個數.如何來求這個Mn，這既是一個排列問題，同時又是一個數列的通項問題.

我們不妨先考慮這個數列的前幾項.整數更列的個數可由解遞歸關系而得到.考慮整數1，2，…，n的更列，對其進行合理分布，恰當分類.

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

顯然，M1=0，M2=1，M3=2.(*)式可進一步變形，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! .

五、容斥原理在更列問題中的應用

例1 4只小鳥飛入四個不同的籠子里，每只小鳥都有自己的一個籠子(不同的鳥，籠子也不同)，每個籠子只能飛進一只鳥，若都不飛進自己的籠子，應有多少種不同的飛法？

解 為了準確地計算出有多少種不同的飛法，先求出4只小鳥隨意飛有多少種不同的飛法，然后減去不符合條件的飛法.

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

根據上面提到的公式：

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

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

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

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

解 設這8個縣的編號為1，2，…，8，而ai為第i號縣（i=1，2，…，8）派出的巡視組.I表示這8個巡視組分派到這8個縣（每縣一組）的所有可能的方法組成的集合，Ai表示I中ai分到i號縣的分配方法組成的集合（i=1，2，…，8）.依題意，根據公式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（種）分配方法，即為所求.

【參考文獻】

［1］李超英.排列和數列的匯合點——有趣的更列問題.中學數學參考，2003（9）：35.

［2］周小華.由“小鳥飛錯鳥籠”談容斥原理的應用.紹興文理學院院報，2001（2）.

［3］吳國柱，郝端緒.容斥原理在組合數學中的若干應用.冀東學刊，1994（6）：23.

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