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

姚簫生

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

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

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

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

1 容斥原理

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

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

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

⑴∩;

⑵.

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

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

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

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

⑶;

⑷;

⑸。

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

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

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

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

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

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

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

由1.4得：

=504

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

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

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

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

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

，S有限集，A、B∈S

由1.4得：

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

3908500338213