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

　　摘 要： 容斥原理是組合數學中的一個重要定理和方法。將這一重要原理應用到排列問題中，會給解決錯位排列、有禁區排列和圓形排列等問題帶來極大的便利。
　　關鍵詞： 容斥原理 錯位排列 有禁區排列 圓形排列
　　
　　容斥原理，又稱包含——排斥原理或取舍原理，它是組合數學中解決計數問題的一個重要原理和工具，若將這一原理應用到排列問題中，則對解決錯位排列、有禁區排列和圓形排列等問題都會起到很大作用.
　　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：數1，2，3，…，9的全排列中，求偶數在原來的位置上，其余都不在原來的位置上的錯排數目.
　　解：此問題實際上是1，3，5，7，9五個數的錯排問題，總數是
　　5！［1-+-+-］=120×（-+-）=44.
　　3.容斥原理在有禁區排列中的應用
　　n個元素的某一排列可以看做是n個棋子在n×n的棋盤C3Ae1+PPVRVbG+6pkkFwhw==上的一種布局。當一個棋子置于棋盤的某一格子時，則這一格子所在的行和列都不能再布任何棋子，即棋盤的每一個布局每行每列有且只有一個棋子.有禁區排列是指每個棋子在棋盤上都有一定的禁區的布局.
　　利用容斥原理可以導出有禁區的排列數為
　　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）！（m=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格式閱讀原文