1、第五講 容斥原理,容斥原理又稱包含排斥原理,它是利用集 合的基本運(yùn)算來(lái)解決實(shí)際問(wèn)題中的大量計(jì)算 問(wèn)題,是組合學(xué)中的一個(gè)基本計(jì)數(shù)理論.,5.1 容斥原理引論,3的倍數(shù)是：3，6，9, 12, 15, 18。6個(gè),例 求1，20中2或3的倍數(shù)的個(gè)數(shù),5.1 容斥原理引論,解 2的倍數(shù)是：2，4，6，8，10，12，14， 16，18，20。 10個(gè),但答案不是10+6=16 個(gè)， 因?yàn)?,12,18在兩類中重復(fù)計(jì)數(shù)，應(yīng)減去。,故答案是：16-3=13,容斥原理研究若干個(gè)有限集合的交或并 的計(jì)數(shù)問(wèn)題。,有,(a),(b),DeMorgan定理 論域U，補(bǔ)集,5.1 容斥原理引論,證：(a)的證明。

2、設(shè) ,則 相當(dāng)于 和 同時(shí)成立，亦即,(1),反之，若,故,(2),由（1）和（2）得,5.1 容斥原理引論,DeMogan定理的推廣：設(shè),5.1 容斥原理引論,最簡(jiǎn)單的計(jì)數(shù)問(wèn)題是求有限集合A和B的 并的元素?cái)?shù)目。顯然有,即具有性質(zhì)A或B的元素的個(gè)數(shù)等于具有 性質(zhì)A和B的元素個(gè)數(shù)減去同時(shí)具有性質(zhì)A和 B的元素個(gè)數(shù)。,(1),定 理：,5.2 容斥原理,U,B,A,證明：,對(duì)于,中的元素,在等式兩邊都恰被,統(tǒng)計(jì)了一次。,可分為如下三種情形來(lái)考慮：,（1）,，但,，則,恰好被統(tǒng)計(jì)了一次；,（2）,，但,，則,恰好被統(tǒng)計(jì)了一次；,（3）,且,，那么必有,，從而,被統(tǒng)計(jì)了,次。,所以，,在等式兩邊被統(tǒng)

3、計(jì)的次數(shù)是相同的。,5.2 容斥原理,定 理：,(2),A,B,C,5.2 容斥原理,例 一個(gè)學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同 時(shí)修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時(shí)修數(shù)學(xué)、 化學(xué)的20人；同時(shí)修物理化學(xué)的22人。同時(shí)修三門 的3人。問(wèn)這學(xué)校共有多少學(xué)生？,解 令：M為修數(shù)學(xué)的學(xué)生集合； P 為修物理的學(xué)生集合； C 為修化學(xué)的學(xué)生集合；,5.2 容斥原理,即學(xué)校學(xué)生數(shù)為336人。,5.2 容斥原理,我們還可推出：,利用數(shù)學(xué)歸納法可得一般的定理：,5.2 容斥原理,定理：設(shè),是有限集合，則,(4),5.2 容斥原理,(5),容斥原理指的

4、就是（4）和（5）式。,5.2 容斥原理,例1 求a,b,c,d,e,f六個(gè)字母的全排列中不允許出現(xiàn)ace和df圖象的排列數(shù)。,解：設(shè)A為ace作為一個(gè)元素出現(xiàn)的排列集，B為 df作為一個(gè)元素出現(xiàn)的排列集， 為同時(shí)出現(xiàn)ace、df的排列數(shù)。,5.3 例題,根據(jù)容斥原理，不出現(xiàn)ace和df的排列數(shù)為：,=6!- (5!+4!)+3!=582,例2 求從1到500的整數(shù)中能被3或5除盡的數(shù)的個(gè)數(shù)。,解：令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合， B為被5除盡的數(shù)的集合。,被3或5除盡的數(shù)的個(gè)數(shù)為,5.3 例題,例3 求由a,b,c,d四個(gè)字母構(gòu)成的n位符號(hào)串中， a,b,c都至少出現(xiàn)一次的符號(hào)

5、串?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)a的n位符號(hào)串的個(gè)數(shù)應(yīng)是,5.3 例題,a，b，c都至少出現(xiàn)一次的n位符號(hào)串集合即為,5.3 例題,例4 求不超過(guò)120的素?cái)?shù)個(gè)數(shù)。,解：因 ，故不超過(guò)120的合數(shù)必然是2、3、5、7的倍數(shù)，而且不超過(guò)120的合數(shù)的因子不可能都 超過(guò)11。,設(shè) 為不超過(guò)120的數(shù) 的倍數(shù)集， =2，3，5，7。,5.3 例題,5.3 例題,5.3 例題,5.3 例題,注意：27并非就是不超過(guò)120的素?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ù)。故所求的不超過(guò)120的素?cái)?shù) 個(gè)數(shù)為：27+4-1=30,5.3 例題,例5 歐拉函數(shù) 是求小于n且與n互素的數(shù)的個(gè)數(shù)。,設(shè)1到n的n個(gè)數(shù)中為 倍數(shù)的集合為,解：若n分解為素?cái)?shù)的乘積,則有,5.3 例題,5.