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

1、第六章 容斥原理及應(yīng)用6.1 是討論和排斥的計(jì)數(shù)問題例: 1,2,3,. 20中2或3的倍數(shù)的個(gè)數(shù)解: 2的倍數(shù)是：2，4，6，8，10，12，14， 16，18，20。 共10個(gè)3的倍數(shù)是：3，6，9，12，15， 18。共 6個(gè)注意：藍(lán)色的數(shù)同時(shí)出現(xiàn)在兩個(gè)序列中。1但答案不該是10+6=16 個(gè)，因?yàn)?，12，18在兩 類中重復(fù)計(jì)數(shù)，應(yīng)減去。故答案是： 163 = 13 容斥原理僅僅研究有限集合的交或并的計(jì)數(shù)。例：對于1,2,n的排列i1, i2, , in，其中 i1 1的排列有多少個(gè)？分析 第一種方法：集合1,2, k-1, k+1, , n的 (n-1) -排列共有(n-1)!。現(xiàn)在

2、將k置于這些2 (n-1) -排列的首位之前，就得到所有以k開始的 n-排列，依然有 (n-1)!個(gè)。由于k不能等于1，所以共有(n-1)(n-1)!個(gè)首位不為1的n-排列。 第二種思路： 1,2,n的排列數(shù)是n!， 2,3,n 的(n-1)-排列數(shù)是(n-1)!，每個(gè)(n-1)-排列的首位前置一個(gè)1，就得到所有首位為1的(n-1)!個(gè)n-排列。于是，首位不為1的n-排列的個(gè)數(shù)是： n! (n-1)! = (n-1)(n-1)！。3例:1到600中不能被6整除的整數(shù)的個(gè)數(shù)是多少？ 分析 1到600共有600個(gè)數(shù)，能被6整除的有： 600/6=100個(gè)。 因此，不能被6整除的數(shù)有600-100=

3、500個(gè)一般來說，對于集合S中的元素定義一種性質(zhì)P，x S ，若x具有性質(zhì)P，則P(x)為真。于是，所有具有性質(zhì)P的元素的集合:4 A=xx S P(x) 而不具性質(zhì)P的元素集合是： = S A=xx S x A = xx S P(x) 顯然 =SA 這就是容斥原理最簡單的例子。將這個(gè)例子給予推廣：令S是一些物體的集合，并令P1和P25 是S的每個(gè)物體可能具有或者不具有的兩個(gè)性質(zhì) 我們目的是為了求出S中即不具有P1也不具有P2的兩性質(zhì)的物體的個(gè)數(shù)，按下列步驟： 先求出S中所有物體的個(gè)數(shù)，然后去掉具有性質(zhì)P1的物體個(gè)數(shù)，再去掉具有性質(zhì)P2的物體個(gè)數(shù)，如果一些物體同時(shí)具有P1和P2兩種性質(zhì)，它們就

4、會(huì)被去掉兩次，那么我們需要再加回這些物體的個(gè)數(shù)，用符號(hào)表示如下：6 令A(yù)1=xx S P1(x) , A2=xx S P2(x) 表示那些即不具有P1也不具有P2性質(zhì)的物體。我們有S =A2A1A1 A27由于上式左邊表示那些既無性質(zhì)P1也無性質(zhì)P2的 物體的個(gè)數(shù)，因此可以通過對等式右邊增加1個(gè)性質(zhì)P1 、P2都不具有的物體，而加其他物體等于給等式右邊增加0個(gè),由此來證明等式的合理性； 如果x是性質(zhì)P1 、P2都不具有的一個(gè)物體，那么它算作S的一個(gè)物體但不算作A1和A2的，并且它也不能算作A1A2的，因此，它的加入8為等式的右邊凈增加：1 0 0 + 0 = 1 物體。 如果x只具有性質(zhì)P1

5、，那么它為等式的右邊凈增加：1 1 0 + 0 = 0 物體。 如果x只具有性質(zhì)P2 ，那么它為等式的右邊凈增加：1 0 1 + 0 = 0 物體。最后，如果x具有性質(zhì)P1 、P2 ，那么它為等式的右邊凈增加：1 1 1 + 1 = 0 物體。 因此等式右邊的變化只與那些S中性質(zhì)P1 、P2 9都不具有的物體個(gè)數(shù)有關(guān)。這就與等式的左邊 達(dá)到一致。更進(jìn)一步，設(shè)S是集合，它上面定義了m個(gè)性質(zhì) Pi（i1, 2, , m）,于是，具有性質(zhì)Pi的元素的集合是： Ai = xx S Pi(x) , i1, 2, , m10對于1, 2, , m的任一r-組合i1, i2, , ir，同時(shí) 具有性質(zhì) 的元

6、素的集合是： 一般情況下，這一集合可能非空，此時(shí)，我們希望計(jì)算同時(shí)不具有性質(zhì)P1, P2, , Pm的集合：11 中有多少個(gè)元素, 容斥原理就是指出如何通 過對確實(shí)具有這些性質(zhì)的物體的計(jì)數(shù)來計(jì)算上述同時(shí)不具有性質(zhì)Pi集合中物體的個(gè)數(shù)。因此，在這種意義下，容斥原理“顛倒”了計(jì)數(shù)過程。 下面的定理是將容斥原理推廣到m個(gè)子集合上的情況，也就是將性質(zhì)推廣m個(gè)： P1, P2, , Pm ；12定理6.1.1 集合S的不具備性質(zhì)P1, P2, , Pm的物 體的個(gè)數(shù)由下式給出:其中，第一個(gè)和對1,2,m的所有1-組合i13進(jìn)行，第二個(gè)和對1,2,m的所有2-組合i, j 進(jìn)行，第三個(gè)和對1,2,m的所有

7、3-組合i, j, k 進(jìn)行等等。m = 2 時(shí)我們已經(jīng)討論過了，當(dāng) m=3 時(shí)上式變成14 當(dāng) m=4 時(shí)上式又變成：m為一般的情況下，公式右邊的展開如下：15公式右邊的項(xiàng)數(shù)有如下情況：16公式的左邊是對 S的不具有性質(zhì)Pi (i=1,2, .m) 的物體的計(jì)數(shù)，對右邊增加1個(gè)性質(zhì)Pi都不具有的物體x。公式右邊的凈增加數(shù)為： 1 0 + 0 0 + 0 + (-1)0m = 1 它在S中而不在其他子集Ai中。考慮恰好具有n (n1)個(gè)性質(zhì)Pi (i=1,2, . n)的物體 y , y 這一個(gè)物體在S中僅占數(shù)量是17由于 y 恰好具有n個(gè)性質(zhì)，它剛好是子集: A1, A2, A3,. Am中

8、恰好n個(gè)的成員，它對 Ai提供數(shù)值為：我們可以以 種方式為y 選擇恰好具有一對性質(zhì)Pi 和Pj ,那么y恰好是形式為AiAj , 那些集合中的 個(gè)成員，因此y給 AiAj 提供數(shù)值為： ,對 AiAj Ak提供數(shù)值為： 18 等等。因此y對于公式右邊提供數(shù)值增加為：因?yàn)閚m，若kn，則 根據(jù)P82恒等式5-4上式為0，因此，如果y至少具有一個(gè)性質(zhì)Pi ，那么它對公式右邊的凈增數(shù)值就是0。19實(shí)際上在集合的運(yùn)算中，我們已經(jīng)接觸過容斥 原理，例如：三個(gè)集合的元素關(guān)系有：ABC=A+B+CABACBC +ABCABC20例：一個(gè)學(xué)校中的某班只開三門課程：數(shù)學(xué)、 物理、化學(xué)。已知修這三門課的學(xué)生分別

9、有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時(shí)修數(shù)學(xué)、化學(xué)的20人；同時(shí)修物理化學(xué)的22人。同時(shí)修三門的3人。問這學(xué)校共有多少學(xué)生？解：令：M為修數(shù)學(xué)的學(xué)生集合； P 為修物理的學(xué)生集合； C 為修化學(xué)的學(xué)生集合；那么：21M=170，P=130，C=120，MP=45 MC=22，PC =20，MPC=3本題的目的是要求出： 的數(shù)字，由容斥原理的公式：MPC=M+P+CMP MCPC +MPC =170+130+120452220+3 =336人22定理：設(shè)Ai (i=1,2,n)是有限集合，則： 證明：用數(shù)學(xué)歸納法證明。已知 n=2時(shí)有： 23 設(shè) n-1時(shí)成立，即有

10、：所以在取n時(shí)就有：24由交、并運(yùn)算的分配律，上式中最后一項(xiàng)有： 25由假設(shè)n-1時(shí)成立n-1個(gè)集合并的元素計(jì)數(shù)公式將這n-1個(gè)兩個(gè)集合交構(gòu)成的并展開：26將n-1時(shí)成立展開式、以及上面的推導(dǎo)結(jié)果代入，原等式的左邊為：由假設(shè)n-1時(shí)成立n-1個(gè)集合并的元素計(jì)數(shù)公式27282930如果利用德.摩根律(De.Mogan)也能得到容斥原理:31例1 求a,b,c,d,e,f六個(gè)字母的全排列中不允許出 現(xiàn)ace和df子串的排列數(shù)。 解：設(shè)A為ace作為一個(gè)元素出現(xiàn)的排列集，B為 df作為一個(gè)元素出現(xiàn)的排列集，AB為同時(shí)出現(xiàn)ace、df的排列數(shù)。所以A= 4??； B= 5??；AB= 3??；根據(jù)容斥原理，

11、不出現(xiàn)ace和df的排列數(shù)為：32例:求從1到1000不能被5,6和8整除的整數(shù)的個(gè)數(shù); 解：我們將兩個(gè)整數(shù)a,b或者三個(gè)整數(shù)a,b,c的最小公倍數(shù)記為：lcma,b或者lcna,b,c. 令P1 P2 P3分別表示能被5,6,8整除的性質(zhì)，S是1到1000的整數(shù)集合。Ai ( i=1,2,3 ) 是那些具有Pi性質(zhì)的子集合，題意是要我們求出：33 首先：同時(shí)被5，6整除即是能被lcm 5, 6 = 30整除，同理lcm 5, 8 = 40 ，lcm 6, 8 = 24，那么：34同理lcm 5, 6, 8 = 120 ，就有：由容斥原理，從1到1000不能被5,6和8整除的整數(shù)的個(gè)數(shù)等于：3

12、5例： 求由a,b,c,d四個(gè)字母構(gòu)成的n位符號(hào)串中， a,b,c至少出現(xiàn)一次的符號(hào)串?dāng)?shù)目。解：令A(yù)、B、C分別為n位符號(hào)串中不出現(xiàn)a,b,c符號(hào)的集合。 由于n位符號(hào)串中每一位都可取a,b,c,d四種符號(hào)中的一個(gè)，故不允許出現(xiàn)各字母的n位符號(hào)串的個(gè)數(shù)應(yīng)是: A=B= C= 3n， AB = AC=BC = 2n36 AB C= 1 a,b,c至少出現(xiàn)一次的n位符號(hào)串集合即為: 它元素個(gè)數(shù)為：37例: 求不超過100的素?cái)?shù)個(gè)數(shù)。解：因 102=100，比10小的素?cái)?shù)有2、3、5、7 故不超過100的合數(shù)必然是2、3、5、7的倍數(shù)，而且不超過100的合數(shù)的因子不可能都超過10，通過求合數(shù)的補(bǔ)集來

13、求素?cái)?shù)個(gè)數(shù)。 設(shè)： Ai為不超過100的數(shù)i的倍數(shù)集， i = 2，3，5，7 。383940 注意：22并非就是不超過100的素?cái)?shù)個(gè)數(shù)， 因?yàn)檫@里排除了2，3，5，7著四個(gè)數(shù)，又包含了1這個(gè)非素?cái)?shù)。2，3，5，7本身是素?cái)?shù)。故所求的不超過100的素?cái)?shù)個(gè)數(shù)為： 22+4-1=25 小于100的素?cái)?shù)它們是： 2， 3， 5， 7，11，13，17，19，23，29， 31， 37，41，43，47，53，59，61，67，71 73，79，83，89，97 共計(jì)：25個(gè)41 在容斥原理中，設(shè)集合的大小僅依賴于k而不依賴于在交中使用了哪k個(gè)集合?；蛘哒fAi它們的基數(shù)一致； AiAj它們的基數(shù)一致;

14、AiAjAk它們的基數(shù)一致;. 這樣就存在常數(shù)0, 1, 2, .m,使得 0=S 1= A1= A2= A3= Am422= A1A2= A2A3= = Am-1Am 3= A1A2A3= Am-2Am-1Am m= A1A2A3 Am-1Am即在Ai= Aj等情況下我們只統(tǒng)計(jì)Ai的個(gè)數(shù)，在這種情況下容斥原理可以簡化成：43這是因?yàn)樵谌莩庠碇谐霈F(xiàn)的第k個(gè)求和包含個(gè)被加數(shù)，并且每個(gè)都等于k例：從0到99999有多少含有數(shù)字2,5,8的整數(shù)。解：設(shè)S是從0到99999的數(shù)字，加前導(dǎo)0就全是44 五位字符串，S就是多重集50,51,52,. 59 的5-排列，令P1,P2 ,P3分別是整數(shù)但不包含有數(shù)字2，5，8這個(gè)性質(zhì)，令A(yù)1,A2 ,A3分別是S中具有性質(zhì)P1,P2 ,P3的整數(shù)集合。題意思求出集合 的元素個(gè)數(shù)。利用前面的知識(shí)可知0= 105， 1= 95，2= 85， 3= 75答案為： 105 - 95- 85- 75 = 105 - 395+385- 75