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

摘 要： 容斥原理是組合數學中的一個重要定理和方法。將這一重要原理應用到排列問題中，會給解決錯位排列、有禁區排列和圓形排列等問題帶來極大的便利。

關鍵詞： 容斥原理 錯位排列 有禁區排列 圓形排列

容斥原理，又稱包含——排斥原理或取舍原理，它是組合數學中解決計數問題的一個重要原理和工具，若將這一原理應用到排列問題中，則對解決錯位排列、有禁區排列和圓形排列等問題都會起到很大作用.

1.容斥原理簡述

（1）簡單形式：設有限集合和與中元素有關的性質集合P={p，p，…，p}，令A={x|x∈S，且x具有性質p}，=S-A（i=1，2，…，n），則|∩∩…∩|=|S|-|A|+|A∩A|-|A∩A∩A|+…+（-1）|A∩A∩…∩A|.

（2）一般形式：設S，P同上，F為一域，對每一a∈S，有唯一w（a）∈F與a對應，稱w（a）為a的權，W（p，p，…，p）為S中同時具有r這個性質p，p，…，p的所有元素的權和，W（r）=∑W（p，p，…，p），其中和式取遍P的r元子集，當r=0時，規定W（0）等于S中所有元素的權的和，令E（k）表示中恰好具有P中k個性質的元素的權和，E（0）表示S中不具有P中任何性質的元素的權和，則有：

E（k）=（-1）mkW（m）?搖?搖?搖?搖E（0）=（-1）W（m）

若對一切a∈S，都有w（a）=1，并以N（m）記W（m），則有

E（k）=（-1）mkN（m）?搖?搖?搖?搖E（0）=（-1）N（m）

2.容斥原理在錯排問題中的應用

錯位排列，又稱為更列，是一種帶限制條件的全排列。若Z={1，2，…，n}，則Z的一個錯位排列是指這樣的全排列aa…a，使a≠i（i=1，2，…，n）.利用容斥原理可以推導的所有錯位排列的個數Dn.

定義性質P：對排列aa…a，有a=i（i=1，2，…，n），設A為具有性質P的全體排列，則Z的所有錯位排列所構成的集合為∩∩…∩.

因數字i不動，故

|Ai|=（n-1）！，i=1，2，…，n.

同理

|A∩A|=（n-2）！，i，j=1，2，…，n，i≠j.

……

由容斥原理得：

D=|∩∩…∩|

=n！-n1（n-1）！+n2（n-2）！-…+（-1）nn0！

=n?。?-+-…+（-1）］

例1：數1，2，3，…，9的全排列中，求偶數在原來的位置上，其余都不在原來的位置上的錯排數目.

解：此問題實際上是1，3，5，7，9五個數的錯排問題，總數是

5?。?-+-+-］=120×（-+-）=44.

3.容斥原理在有禁區排列中的應用

n個元素的某一排列可以看做是n個棋子在n×n的棋盤上的一種布局。當一個棋子置于棋盤的某一格子時，則這一格子所在的行和列都不能再布任何棋子，即棋盤的每一個布局每行每列有且只有一個棋子.有禁區排列是指每個棋子在棋盤上都有一定的禁區的布局.

利用容斥原理可以導出有禁區的排列數為

n！-r（n-1）！+r（n-2）！-…±r，

其中r是有i個棋子布置到禁區部分的方案數.

令PP…P為n個棋子布入n×n棋盤所得到的排列，其中P為第i個棋子落在棋盤的第i行的位置.A為第i個棋子放入禁區，即P在禁區內事件.

一個棋子落入禁區方案數為r，剩下的n-1個棋子為無限制條件的排列，故至少有一個棋子進入禁區的方案數為r（n-1）！.兩個棋子落入禁區方案數為r，而其余n-2個棋子為無限制條件的排列，故至少有兩個棋子進入禁區的方案數為r（n-2）！，依此類推.

依據容斥原理，布個棋子無一落入禁區的方案數應為：

|∩∩…∩|=n！-r（n-1）！+r（n-2）！-…±r.

例2：有甲，乙，丙，丁四個人，A，B，C，D為四項任務，甲不能從事任務B；乙不能從事B，C兩項任務；丙不能從事C，D任務；丁不能從事任務D.若要求每人從事各自力所能及的一項任務，試問有多少種不同方案？

分析：每一種分配方案相當于圖1的關于A，B，C，D的有禁區排列（陰影表示禁區）.問題也相當于求在如圖1所示的有禁區的棋盤上，用四個棋子進行布局的方案數，因此需用到棋盤多項式.

解：圖1的禁區的棋盤多項式為1+6x+10x+4x，

即r=6，r=10，r=4

所求方案數為：

4！-6×3！+10×2！-4=4.

4.容斥原理在圓形排列中的應用

問題：將1，1′，2，2′，…，n，n′排成一個圓圈，當i，i′（i=1，2，…，n）相鄰時，則將i，i′看作一個整體而不考慮它們之間的順序，求這種圓形排列的個數R.

應用容斥原理的一般形式，我們可以得到R的公式.

設S為1，1′，2，2′，…，n，n′的所有圓形排列的集合，P表示性質“排列中i，i′相鄰”（i=1，2，…，n），則：

R=E（0）+E（1）+E（2）+…+E（n）=E（k）.

易知，N（m）=nm2（2n-m-1）?。╩=0，1，…，n），由容斥原理知

E（k）=（-1）mkN（m），

故

R=E（k）=（-1）mkN（m）

=（-1）mkN（m）=（-1）mkN（m）

=（-1）mkN（m）=（-1）mkN（m）

=（-1）［（-1）mkN（m）］=（-1）N（m）

=（-1）nm（2n-m-1）！

例3：當n=2時，R=20•3！-21•2！+22•1！=3.

以上僅是容斥原理被應用到排列中的幾個方面，而它在排列問題中的應用遠不止這些，在其他類型的排列求解中也經常被使用.

參考文獻：

［1］陳敬華.容斥原理及其應用［J］.高等函授學報（自然科學版），2000，13，（2）：17.

［2］柯召，魏萬迪.組合論［M］.北京：科學出版社，1981.

［3］盧開澄.組合數學［M］.北京：清華大學出版社，1991.

［4］盧青林，劉光乾.一類排列問題的計數［J］.徐州師范大學學報（自然科學版），1998，16，（2）：17.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文