容斥原理在組合學(xué)中的相關(guān)應(yīng)用

姚簫生

摘 要：人類(lèi)在發(fā)展生產(chǎn)和生活的過(guò)程中，難免會(huì)遇到很多計(jì)數(shù)問(wèn)題，而有些計(jì)數(shù)問(wèn)題，用直接的方法比較難以解決，在前人的經(jīng)驗(yàn)基礎(chǔ)之上，人們探索并創(chuàng)立了一種新的計(jì)數(shù)方法，其中就有容斥原理。本文通過(guò)研究運(yùn)用容斥原理解決組合學(xué)中的組合計(jì)數(shù)問(wèn)題的相關(guān)步驟及相關(guān)的題型，總結(jié)哪類(lèi)組合計(jì)數(shù)問(wèn)題可以運(yùn)用容斥原理解決以及容斥原理解決這類(lèi)問(wèn)題的相關(guān)步驟。

關(guān)鍵詞：容斥原理;排列;組合學(xué)

本文的工作就是總結(jié)出哪類(lèi)組合計(jì)數(shù)問(wèn)題可以運(yùn)用容斥原理解決，以及總結(jié)出運(yùn)用容斥原理解決這類(lèi)組合計(jì)數(shù)問(wèn)題的大致步驟。

本文主要討論容斥原理在組合學(xué)中的應(yīng)用。

1 容斥原理

容斥原理是由英國(guó)數(shù)學(xué)家詹姆斯·約瑟夫·西爾維斯特19世紀(jì)首次創(chuàng)立[10]。

我們知道運(yùn)用容斥原理求解問(wèn)題時(shí)，是將直接求解轉(zhuǎn)換為間接求解，我們大學(xué)學(xué)過(guò)一個(gè)簡(jiǎn)單的定理，De Morgan定理。

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

⑴∩;

⑵.

運(yùn)用容斥原理求解時(shí)常會(huì)用到一些簡(jiǎn)單但又重要的基本公式。

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

⑴當(dāng)時(shí)，;

⑵當(dāng)時(shí)，;

⑶;

⑷;

⑸。

在求解問(wèn)題時(shí)，我們要解決的要么是求，或是求，這兩個(gè)我們其實(shí)可以把它們看成是對(duì)偶的，求解上述兩個(gè)公式的值，就需要用到文獻(xiàn)[11]中的兩個(gè)定理：

2 容斥原理在組合計(jì)數(shù)中的相關(guān)應(yīng)用

2.1 對(duì)元素在位置上存在限制的計(jì)數(shù)問(wèn)題

這類(lèi)問(wèn)題也稱(chēng)為“錯(cuò)排問(wèn)題”或者“重排問(wèn)題”，由于錯(cuò)排問(wèn)題最早被尼古拉·伯努利和歐拉研究，因此歷史上也稱(chēng)為伯努利—?dú)W拉的裝錯(cuò)信封問(wèn)題：在寫(xiě)信時(shí)將n封信裝到n個(gè)不同的信封里，有多少種全部裝錯(cuò)信封的情況？其已有的結(jié)果是共有種不同的裝法。

例（排課表問(wèn)題）某班級(jí)某一天的課程安排表要安排6門(mén)課程：語(yǔ)文、數(shù)學(xué)、英語(yǔ)、物理、化學(xué)、生物，規(guī)定每門(mén)課上僅且上一節(jié)，一天共安排六節(jié)課，并且生物不排在第一節(jié)，數(shù)學(xué)不排在最后一節(jié)，那么符合這種規(guī)定的課表有多少種不同的排法？

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

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

由1.4得：

=504

答：符合規(guī)定的課表有504種排法。

2.2 對(duì)元素相鄰位置存在限制的計(jì)數(shù)問(wèn)題

此類(lèi)問(wèn)題亦稱(chēng)為“夫妻問(wèn)題”，最先是由法國(guó)數(shù)學(xué)家魯卡斯在1891年提出的：今需安排n對(duì)夫妻圍圓桌（2n個(gè)座位已編號(hào)）而坐，男女相間，夫妻不相鄰，問(wèn)有多少種不同的安排座法？已有的結(jié)果為：。

例甲、乙、丙、丁四名同學(xué)到一所學(xué)校實(shí)習(xí)，現(xiàn)有四個(gè)班級(jí)A、B、C、D，現(xiàn)將甲、乙、丙、丁四名同學(xué)分別分到這四個(gè)班級(jí)中，每個(gè)班級(jí)有且僅有一名同學(xué)，同時(shí)要求甲、乙兩名同學(xué)所分到的班級(jí)不相鄰，丙、丁兩名同學(xué)所分到的班級(jí)不相鄰，試問(wèn)滿足這種條件的排法有多少種？

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

，S有限集，A、B∈S

由1.4得：

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

3 容斥原理求解組合計(jì)數(shù)問(wèn)題的步驟總結(jié)

第一種：能夠直接利用容斥原理解決的，即限制的是元素位置的計(jì)數(shù)問(wèn)題。

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

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

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

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

第1步：首先我們?cè)陬}目中所給的集合中任取出一個(gè)元素，用s（可以是任意一個(gè)小寫(xiě)字母）表示，若s滿足題中條件的肯定，則用表示s具有相對(duì)應(yīng)的性質(zhì)。（此處“條件的肯定”是指不出現(xiàn)否定詞，如：不能被7和9整除的，我們要改成“能被7和9整除”，如果題目中的限制條件本來(lái)不含有否定詞，則不用改。）

第2步：運(yùn)用進(jìn)行求解即可。其中以表示S中不具有中任一個(gè)性質(zhì)的元素個(gè)數(shù) 。若第i個(gè)限制條件已經(jīng)是肯定的了，我們就不用1去減了，直接寫(xiě)上ai，同時(shí)在等號(hào)前面里，ai不需要標(biāo)上標(biāo)。

通過(guò)上述例題的求解，我們不難發(fā)現(xiàn)，運(yùn)用容斥原理求解排列組合計(jì)數(shù)問(wèn)題的時(shí)候，就是把直接求解轉(zhuǎn)換為間接求解，且在計(jì)算的過(guò)程中，若過(guò)多算了，我們就排除多算的部分，如果排除的多了，我們就再加上多排除的部分，如此類(lèi)推下去，直至所求結(jié)果既不多也不少。這就是應(yīng)用容斥原理求解的核心思路。

參考文獻(xiàn)：

[1]曹汝成.廣義容斥原理及其應(yīng)用[J].數(shù)學(xué)研究與評(píng)論，1988，8（4）：526-530.

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

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

[4]盧開(kāi)澄，盧華明.組合數(shù)學(xué)[M]（第4版）.北京：清華大學(xué)出版社，2006，119-133.