容斥原理在組合學中的相關應用

姚簫生

摘 要：人類在發展生產和生活的過程中，難免會遇到很多計數問題，而有些計數問題，用直接的方法比較難以解決，在前人的經驗基礎之上，人們探索并創立了一種新的計數方法，其中就有容斥原理。本文通過研究運用容斥原理解決組合學中的組合計數問題的相關步驟及相關的題型，總結哪類組合計數問題可以運用容斥原理解決以及容斥原理解決這類問題的相關步驟。

關鍵詞：容斥原理;排列;組合學

本文的工作就是總結出哪類組合計數問題可以運用容斥原理解決，以及總結出運用容斥原理解決這類組合計數問題的大致步驟。

本文主要討論容斥原理在組合學中的應用。

1 容斥原理

容斥原理是由英國數學家詹姆斯·約瑟夫·西爾維斯特19世紀首次創立[10]。

我們知道運用容斥原理求解問題時，是將直接求解轉換為間接求解，我們大學學過一個簡單的定理，De Morgan定理。

1.1 De Morgan定理：若A和B是全集U的子集，則：

⑴∩;

⑵.

運用容斥原理求解時常會用到一些簡單但又重要的基本公式。

1.2基本公式：設S是有限集，A、B、C∈S

⑴當時，;

⑵當時，;

⑶;

⑷;

⑸。

在求解問題時，我們要解決的要么是求，或是求，這兩個我們其實可以把它們看成是對偶的，求解上述兩個公式的值，就需要用到文獻[11]中的兩個定理：

2 容斥原理在組合計數中的相關應用

2.1 對元素在位置上存在限制的計數問題

這類問題也稱為“錯排問題”或者“重排問題”，由于錯排問題最早被尼古拉·伯努利和歐拉研究，因此歷史上也稱為伯努利—歐拉的裝錯信封問題：在寫信時將n封信裝到n個不同的信封里，有多少種全部裝錯信封的情況？其已有的結果是共有種不同的裝法。

例（排課表問題）某班級某一天的課程安排表要安排6門課程：語文、數學、英語、物理、化學、生物，規定每門課上僅且上一節，一天共安排六節課，并且生物不排在第一節，數學不排在最后一節，那么符合這種規定的課表有多少種不同的排法？

解 設所求結果數為N，令S表示為這六門課做成所有不同全排列所成之集，A表示為生物課排在第一節做成的所有不同全排列所成之集，B表示為數學課排在最后一節做成的所有不同全排列所成之集。則，我們可以得到：

，S為有限集，A、B∈S。

由1.4得：

=504

答：符合規定的課表有504種排法。

2.2 對元素相鄰位置存在限制的計數問題

此類問題亦稱為“夫妻問題”，最先是由法國數學家魯卡斯在1891年提出的：今需安排n對夫妻圍圓桌（2n個座位已編號）而坐，男女相間，夫妻不相鄰，問有多少種不同的安排座法？已有的結果為：。

例甲、乙、丙、丁四名同學到一所學校實習，現有四個班級A、B、C、D，現將甲、乙、丙、丁四名同學分別分到這四個班級中，每個班級有且僅有一名同學，同時要求甲、乙兩名同學所分到的班級不相鄰，丙、丁兩名同學所分到的班級不相鄰，試問滿足這種條件的排法有多少種？

解 設所求結果數為N，令S表示為四名同學做成的所有不同全排列所成之集，A表示為甲、乙兩名同學所在班級相鄰做成的所有不同全排列所成之集，B表示為丙、丁兩名同學所在班級相鄰做成的所有不同全排列所成之集，同時把甲、乙兩名同學捆綁在一起算作一個，把丙、丁兩名同學捆綁在一起算作一個，則我們可以得到：

，S有限集，A、B∈S

由1.4得：

答：滿足題中所述條件的排法有8種。

3 容斥原理求解組合計數問題的步驟總結

第一種：能夠直接利用容斥原理解決的，即限制的是元素位置的計數問題。

第1步：先用N表示為所求結果數，然后再用一個大寫字母S（可以是任意一個不同于N的字母）表示為n個相異元組成的所有不同全排列所成之集，并求出這個全排列的個數。

第2步：如果題目中存在個限制性條件，則我們用不同于第1步的相應個數的大寫字母A，B，C···表示出這k個限制性條件的否定做成的所有不同全排列所成之集。同時也求出相應的排列個數等。（這些排列個數的求法在高中已經學過，在此就不再給出方法）

第3步：利用公式求出具體的結果。

第二種：無法直接利用容斥原理解決的，即限制元的條件不是在位置上，而是其他一些限制的計數問題。

第1步：首先我們在題目中所給的集合中任取出一個元素，用s（可以是任意一個小寫字母）表示，若s滿足題中條件的肯定，則用表示s具有相對應的性質。（此處“條件的肯定”是指不出現否定詞，如：不能被7和9整除的，我們要改成“能被7和9整除”，如果題目中的限制條件本來不含有否定詞，則不用改。）

第2步：運用進行求解即可。其中以表示S中不具有中任一個性質的元素個數 。若第i個限制條件已經是肯定的了，我們就不用1去減了，直接寫上ai，同時在等號前面里，ai不需要標上標。

通過上述例題的求解，我們不難發現，運用容斥原理求解排列組合計數問題的時候，就是把直接求解轉換為間接求解，且在計算的過程中，若過多算了，我們就排除多算的部分，如果排除的多了，我們就再加上多排除的部分，如此類推下去，直至所求結果既不多也不少。這就是應用容斥原理求解的核心思路。

參考文獻：

[1]曹汝成.廣義容斥原理及其應用[J].數學研究與評論，1988，8（4）：526-530.

[2]孫淑玲，許胤龍.組合數學引論[M].合肥：中國科技大學出版社，1999，97-119.

[3]潘永亮，徐俊明.組合數學[M].北京：科學出版社，2006，43-46.

[4]盧開澄，盧華明.組合數學[M]（第4版）.北京：清華大學出版社，2006，119-133.

3908500338213