容斥原理及其應(yīng)用

夏婧

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

關(guān)鍵詞：計數(shù)問題;容斥原理;奧數(shù)

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

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

A1∪A2∪……∪An=A

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

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

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

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

上述情況推廣到3個集合時，如圖2所示，相應(yīng)地有結(jié)論：

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

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

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

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

證明對n用數(shù)學(xué)歸納法。

當(dāng)n=2時，即為|A∪B|=|A|+|B|-|A∩B|，設(shè)（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）

由歸納假設(shè)：

|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），再由歸納假設(shè)：

|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（逐步淘汰原理）設(shè)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。

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

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

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

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

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

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

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

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

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

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

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

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

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

由逐步淘汰原理，

|……|=|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這個數(shù)字不起特別的作用。全部推導(dǎo)對于任意n份信箋和n個信封的一般情形依然有效。

容斥原理不僅在關(guān)于計數(shù)的解答問題中有廣泛的應(yīng)用，有的證明題中將容斥原理與推理結(jié)合起來，也有很好的效果。

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

這里再給出可以應(yīng)用容斥原理解決的問題作為練習(xí)。

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

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

[參考文獻]

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

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

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