容斥原理及其應用

夏婧

摘? ?要：容斥原理是奧數的四大原理之一，是考生們繞不過去的知識點。孩子學習奧數，家長一定要讓孩子掌握容斥原理解題方法。

關鍵詞：計數問題;容斥原理;奧數

計數問題是數學競賽中常見的一類問題，很自然地，若用集合的觀點去看計數問題，則計數問題就是要求某一特定集合的元素個數，從而可以利用集合的包含與排除關系，利用集合的交、并、補運算使計數問題轉化，使問題得到解決。這種問題解決的策略就是容斥原理。

若對于有限集合A，當A1，A2，……，An是其一個分劃，即：

A1∪A2∪……∪An=A

Ai∩Aj=Φ，（i，j = 1，2，3，……，n且i≠j）

此時，有|A|=|A1|+|A2|+……+|An|。這就是組合計數中的加法原理，基本思想是把不易計數的有限集A分成若干彼此不相交的容易計數的子集A1，A2，……，An，分別計算各子集元素的個數，從而得到集合A的元素個數。

給出的有限集A一般容易找到這樣的若干子集A1，A2，……，An，使得A=A1∪A2∪……∪An，但往往難以滿足條件Ai∩Aj=Φ，（i，j = 1，2，3，……，n且i≠j），若按加法原理會將A中的元素重復計算。這種情況下，希望能“多退少補”地對加法原理計算得到的結果進行修正，即重復計數（多的）部分減去，若減得太多了再補上，直至結果剛好為|A|。這就是容斥原理的基本思想[1]。

為了幫助理解，先來看簡單的情況。如圖1所示，若集合A，B，S滿足A∪S，B∪S，且A∪B=S，A∩B≠Φ，則易知|S|=|A∪B|=|A|+|B|-|A∩B|。

上述情況推廣到3個集合時，如圖2所示，相應地有結論：

|S|=|A∪B∪C|=|A|+|B|+|C|-（|A∩B|+|A∩C|+|B∩C|）+|A∩B∩C|

若推廣到n個集合時，有：

定理1（容斥原理）設A1，A2，……，An是有限集S的子集，S=A1∪A2∪……∪An，則：

|S|=|A1∪A2∪……∪An|=-++……+（-1）n-1|A1∩A2∩……∩An| （1）

證明對n用數學歸納法。

當n=2時，即為|A∪B|=|A|+|B|-|A∩B|，設（1）對k≤n成立。

下面證明（1）對n+1成立。

記A=A1∪A2∪……∪An，則S=A∪An+1，由公式|A∪B|=|A|+|B|-|A∩B|，有：

|S|=|A|+|An+1|-|A∩An+1|? ? ? （2）

由歸納假設：

|A|=|A1∪A2∪……∪An|=-++……+（-1）n-1|A1∩A2∩……∩An| （3）

又：|A∪An+1|=（A1∪A2∪……∪An）∩An+1=（A1∩An+1）∪（A2∩An+1）∪……∪（An∩An+1），再由歸納假設：

|An∩An+1|=-++……+（-1）n-1|A1∩A2∩……∩An∩An+1|（4）

把（3）、（4）代入（2），|S|=-++……+（-1）n|A1∩A2∩……∩An+1|。

這就證明了容斥原理成立。

若S中的子集為A，S對A的補集記為A—的話，由定理1容易得到容斥原理的另一種形式。

定理2（逐步淘汰原理）設A1，A2，……，An是集合S的子集，則：

……|=S-+-+……+（-1）n| A1∩A2∩……∩An |

顯然，A1∪A2∪……∪An與……是集合S的一個劃分，即：

S=（A1∪A2∪……∪An）∪（……）

且（A1∪A2∪……∪An）∩（……）=Φ。

由加法原理：|S|=|A1∪A2∪……∪An|+|……|。

再由定理1即得定理2。

容斥原理是加法原理的一個推廣（當A1，A2，……，An兩兩不相交時，容斥原理即為加法原理），是組合計數的一個重要工具[2]。

例1：求在小于1 000的正整數中能被7或11整除的數的個數。

解：設A=﹛小于1 000的正整數中能被7整除的數﹜

B=﹛小于1 000的正整數中能被11整除的數﹜

|A|=[]=142，|B|=[]=90，|A∩B|=[]=12

由容斥原理，|A∪B|=|A|+|B|-|A∩B|=142+90-12=220。

上例是容斥原理的一個簡單應用，問題的反面可以用逐步淘汰法解決，于是把問題作些改動就得到下面的競賽題目。

例2（第4屆莫斯科數學競賽題）：在小于1 000的正整數中，既不能被5整除也不能被7整除的有多少個？

解：設S=﹛小于1 000的正整數﹜;A=﹛小于1 000的正整數中能被5整除的數﹜;B=﹛小于1 000的正整數中能被7整除的數﹜。則：

|A|=[]=199， |B|=[]=142， |A∩B|=[]=28

||=S-（|A|+|B|）+|A∩B|=999-（199+142）+28=686

例3（1960年-1961年波蘭數學競賽題）：某人給6個不同的收信人寫了6封信，并且準備了6個寫有收信人地址的信封。有多少種投放信箋的方法，使每份信箋與信封上的收信人都不相符？

解：設I為所有的裝法構成的集合，則顯然有I=6！，我們用1，2，3，4，5，6分別對信和信封編號，記Ai（i=1，2，…，6）為第i封信恰好裝入第i個信封的所有裝法構成的集合，則為第i封信不裝進第i個信封的所有裝法構成的集合，而所求的全部裝錯的裝法的集合即為……。

由逐步淘汰原理，

|……|=|I|-+-+……+（-1）6 | A1∩A2∩……∩A6|

|Ai|=（6-1）！=5！=120， |Ai∩Aj|=（6-2）！=4！=24，……

|A1∩A2∩……∩Ak|=（6-k）！，| A1∩A2∩……∩A6|=（6-6）！=0！=1

所以：|……|=6！-120+24-6+2-+=256。

在上題的解答中，6這個數字不起特別的作用。全部推導對于任意n份信箋和n個信封的一般情形依然有效。

容斥原理不僅在關于計數的解答問題中有廣泛的應用，有的證明題中將容斥原理與推理結合起來，也有很好的效果。

由上面的例子可以看出，容斥原理解決的問題大多涉及某一對象集合A滿足性質集合P中的某些性質的元素的計數問題[3]。如A中不具備P中任何性質的元素個數有多少，A中至少具備P中r個性質的元素個數是多少，或A中恰好具備P中r個性質的元素的個數是多少等。

這里再給出可以應用容斥原理解決的問題作為練習。

示例1，參加大型團體表演的學生共240名，他們面對教練站成一行，自左至右按1，2，3，4，5，……依次報數，教練要求全體學生牢記各自所報的數，并做下列動作：先讓報的數是3的倍數的全體同學向后轉;接著讓報的數是5的倍數的全體同學向后轉;最后讓報的數是7的倍數的全體同學向后轉。問：（1）此時還有多少名同學面對教練？（2）面對教練的同學中，自左至右第66位同學所報的數是幾？[參考答案：（1）136人;（2）118]

示例2，給出1 978個集合，每個集合都恰有40個元素，每兩個集合都恰有一個公共元素，求這1 978個集合的并集所含元素的個數。（參考答案：77 143）

[參考文獻]

[1]費振鵬.例析數學競賽中的計數問題[J].中學數學月刊，2003（10）：44.

[2]周春荔.例談用容斥原理證明問題[J].數學通訊，2002，2（4）：86.

[3]陳傳理，張同君.競賽數學教程[M].北京：高等教育出版社，2000.