組合數(shù)學(xué)第二講

1、容斥原理和鴿巢原理,§1 容斥原理,例 求[1，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è))但答案不是10+6=16 個(gè)，因?yàn)?，12，18在兩類中重復(fù)計(jì)數(shù)，應(yīng)減去。故答案是：16-3=13,容斥原理和鴿巢原理,容斥原理研究有限集合的交或并的計(jì)數(shù)。,[DeMor

2、gan定理] :,容斥原理和鴿巢原理,DeMogan定理的推廣：,設(shè)：,容斥原理和鴿巢原理,容斥原理：,最簡(jiǎn)單的計(jì)數(shù)問題是求有限集合A和B的并的元素?cái)?shù)目。顯然有,容斥原理和鴿巢原理,容斥原理和鴿巢原理,例：一個(gè)學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時(shí)修數(shù)學(xué)、化學(xué)的20人；同時(shí)修物理化學(xué)的22人。同時(shí)修三門的3人。問這學(xué)校共有多少學(xué)生？,解：令，M為修

3、數(shù)學(xué)的學(xué)生集合； P 為修物理的學(xué)生集合； C 為修化學(xué)的學(xué)生集合；所以有,容斥原理和鴿巢原理,即學(xué)校學(xué)生數(shù)為336人。,容斥原理和鴿巢原理,一般地，我們可得定理：,定理：設(shè)A1,A2, …,Am均為有限集，m≥2,則,容斥原理和鴿巢原理,，其中N是集合U的元素個(gè)數(shù)，即不屬于A的元素個(gè)數(shù)等于集合的全體減去屬于A的元素的個(gè)數(shù)。一般有：,容斥原理指的就是這兩個(gè)式子。,容斥原理和

4、鴿巢原理,例1 求a,b,c,d,e,f六個(gè)字母的全排列中不允許出現(xiàn)ace和df圖象的排列數(shù)。,解：設(shè)A為ace作為一個(gè)元素出現(xiàn)的排列集， B為 df作為一個(gè)元素出現(xiàn)的排列集， 則A∩B 為同時(shí)出現(xiàn)ace、df的排列數(shù)。,根據(jù)容斥原理，不出現(xiàn)ace和df的排列數(shù)為：,=6!- (5!+4!)+3!=582,容斥原理和鴿巢原理,例2 求從1到500的整數(shù)中能被3或5除盡的數(shù)的個(gè)數(shù)。,解

5、： 令 A為從1到500的整數(shù)中被3除盡的數(shù)的集合， B為被5除盡的數(shù)的集合,則,容斥原理和鴿巢原理,例3 求由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)a的n位符號(hào)串的個(gè)數(shù)應(yīng)是：3n。,容斥原理和鴿巢原理,a，b，c

6、至少出現(xiàn)一次的n位符號(hào)串集合即為,容斥原理和鴿巢原理,§2 錯(cuò)排問題,n個(gè)元素依次給以標(biāo)號(hào)1，2，…，n。n個(gè)元素的全排列中，求每個(gè)元素都不在自己原來位置上的排列數(shù)。,設(shè) Ai 為數(shù) i 在第 i 位上的全體排列，i =1，2，…，n。因數(shù)字 i 不能動(dòng)，因而有：,容斥原理和鴿巢原理,所以每個(gè)元素都不在原來位置的排列數(shù)為,容斥原理和鴿巢原理,例1 數(shù)1，2，…，9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置的錯(cuò)

7、排數(shù)目。,解：實(shí)際上是1，3，5，7，9五個(gè)數(shù)的錯(cuò)排問題，總數(shù)為：,容斥原理和鴿巢原理,例2. 在8個(gè)字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個(gè)字母不在原來上的錯(cuò)排數(shù)目。,解： 8個(gè)字母的全排列中，令A(yù)1,A2,A3,A4分別表A,C,E,G在原來位置上的排列，則錯(cuò)排數(shù)為：,容斥原理和鴿巢原理,§3 棋盤多項(xiàng)式和有限制排列,例　4個(gè)x ，3個(gè)y，2個(gè)z的全排列中，求不出現(xiàn)xxxx，yyy，z

8、z的排列。 解　設(shè)出現(xiàn)xxxx的排列的集合記為A1， |A1|= 6!/(1! ×3! ×2!) =60; 設(shè)出現(xiàn)yyy的排列的集合記為A2， | A2|= 7!/(4! ×1! ×2!) =105； 設(shè)出現(xiàn)zz的排列的集合記為A3， | A3|= 8!/(4! ×3! &

9、#215;1!) =280；,1. 有限制排列,容斥原理和鴿巢原理,同時(shí)有： |A1∩A2|=4!/ (1! ×2! ×1!) =12； |A1∩A3|= 5!/(1! ×3! ×1!) =20； |A2∩A3|= 6!/(4! ×1! ×1!) =30； |A1∩A2∩A3|=3!=6； 全排列的個(gè)數(shù)為: 9!/(4! ×

10、3! ×2!) =1260；所以： |A1∩A2∩A3|=1260－(60+105+280) +(12+20+30)－6 =871,容斥原理和鴿巢原理,2．棋子多項(xiàng)式,,,,,,,,,,n個(gè)不同元素的一個(gè)全排列可看做n個(gè)相同的棋子在n×n的棋盤上的一個(gè)布局。布局滿足同一行（列）中有且僅有一個(gè)棋子,x,x,x,x

11、,x,如圖所示的布局對(duì)應(yīng)于排列41352。,容斥原理和鴿巢原理,可以把棋盤的形狀推廣到任意形狀：,布子規(guī)定稱為無對(duì)攻規(guī)則，棋子相當(dāng)于象棋中的車。 令r k（C）表示k個(gè)棋子布到棋盤C上的方案數(shù)。如：,容斥原理和鴿巢原理,為了形象化起見，（ ）中的圖象便是棋盤的形狀。,容斥原理和鴿巢原理,規(guī)定 r0(C)=1，包括C=f 時(shí)。設(shè)Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤。　在

12、上面定義下，顯然有　　rk(C)=rk－1(Ci)＋rk(Ce)，,容斥原理和鴿巢原理,即對(duì)任一指定的格子，要么布子，所得的方案數(shù)為 rk－1(Ci)；　要么不布子，方案數(shù)為 rk(Ce)。,設(shè)C有n個(gè)格子，則 r1(C)＝n．r1(C)＝r0(Ci) + r1(Ce)，∵　r1(Ce)＝n－1∴ r0(Ci)＝1．故規(guī)定 r0(C)＝1是合理的．,容斥原理和鴿巢原理,對(duì)任一指定的格子，要么布子，所得的方案數(shù)為 rk－1(Ci)

13、；　要么不布子，方案數(shù)為 rk(Ce)。,=xR(Ci) + R(C e) (3),容斥原理和鴿巢原理,例如：,容斥原理和鴿巢原理,如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒有C2的格子。則有,∴ R(C) = R(C1) R(C2) (4),容斥原理和鴿巢原理,利用前面的式子，可以把一個(gè)比較復(fù)雜的棋盤逐步分解成相對(duì)比較簡(jiǎn)單的棋盤，從而得到其棋盤多項(xiàng)式。,容斥原理和鴿巢原理,３．有禁區(qū)

14、的排列,例 設(shè)對(duì)于排列P=P1 P2 P3 P4, 規(guī)定P1≠３,P２≠１、４， P３≠2、４， P4≠2。,這樣的排列對(duì)應(yīng)于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。,容斥原理和鴿巢原理,定理　設(shè) ri 為 i個(gè)棋子布入禁區(qū)的方案數(shù)，i =1,2,3,···,n。有禁區(qū)的布子方案數(shù)（即禁區(qū)內(nèi)不布子的方案數(shù)）為,例?。?２,３,４四位工人，A, B, C, D四項(xiàng)任務(wù)。條件如下：１不干B；２不

15、干B、C；３不干 C、D；４不干D。問有多少種可行方案？,容斥原理和鴿巢原理,解　由題意，可得如下棋盤：,其中有影線的格子表示禁區(qū)。,方案數(shù)=4!－6(4－1)!+10(4－2)!－4(4－3)! +0(4－4)!=4,容斥原理和鴿巢原理,§4　鴿巢原理之一,鴿巢原理是組合數(shù)學(xué)中最簡(jiǎn)單也是最基本的原理，也叫抽屜原理。即,“若有n個(gè)鴿子巢，n+1個(gè)鴿子，則至少有一個(gè)巢內(nèi)有至少有兩個(gè)鴿子?！?例

16、１　367人中至少有２人的生日相同。例２　10雙手套中任取11只，其中至少有兩只是完整配對(duì)的。例３　參加一會(huì)議的人中至少有２人認(rèn)識(shí)的別的參加者的人數(shù)相等。,容斥原理和鴿巢原理,例４　從1到2n的正整數(shù)中任取n+1個(gè)，則這n+1個(gè)數(shù)中，至少有一對(duì)數(shù)，其中一個(gè)是另一個(gè)的倍數(shù)。,證　設(shè)n+1個(gè)數(shù)是 a1 , a2 , ··· , an+1。每個(gè)數(shù)去掉一切2的因子，直至剩下一個(gè)奇數(shù)為止。組成序列 r1 ,

17、r2, , ··· , rn+1。這n+1個(gè)數(shù)仍在［1 , 2n]中，且都是奇數(shù)。而[1 , 2n]中只有n個(gè)奇數(shù) . 故必有 ri = rj = r , 則 ai = 2αi r, aj = 2αj r .若αi＞αj ，則 ai 是 aj 的倍數(shù)。,容斥原理和鴿巢原理,例５　設(shè) a1 , a2 , ··· , am是正整數(shù)序列，則至少存在k和 l , 1≤k≤ l ≤m，

18、使得和　ak + ak+1 + ··· + al 是m的倍數(shù)。,證　設(shè)Sh = ∑ai , Sh≡ rh mod m 0≤rh≤m-1h = 1 , 2 , ··· , m . 若存在 l , Sl≡0 mod m 則命題成立．否則，1≤rh≤m-1．但h = 1 , 2 , ··· , m．由鴿巢原理，故存在 rk = rh ,

19、即Sk≡ Sh，不妨設(shè) h ＞k．則 Sh－Sk = ak+1 + ak+2 +… + ah ≡0 mod m,i=1,h,容斥原理和鴿巢原理,例６　設(shè) a1 , a2 , a3為任意３個(gè)整數(shù)，b1b2b3為a1 , a2 , a3的任一排列，則 a1－b1 , a2－b2 , a3－b3中至少有一個(gè)是偶數(shù)．,證　由鴿巢原理， a1 , a2 , a3必有兩個(gè)同奇偶．設(shè)這３個(gè)數(shù)被２除的余數(shù)為 xxy，于是b1 , b2

20、, b3中被２除的余數(shù)有２個(gè)x，一個(gè)y．這樣a1－b1 , a2－b2 , a3－b3被２除的余數(shù)必有一個(gè)為０．,容斥原理和鴿巢原理,§5　鴿巢原理之二,鴿巢原理二　m1 , m2 , … , mn都是正整數(shù)，并有m1 + m2 +… +mn－n + 1個(gè)鴿子住進(jìn)n個(gè)鴿巢，則至少對(duì)某個(gè) i 有第 i 個(gè)巢中至少有mi個(gè)鴿子，i = 1 , 2 , … , n．,上一小節(jié)的鴿巢原理一是這一原理的特殊情況，即m1 = m2

21、= … = mn= 2，　 m1 + m2 +… +mn－n + 1 = n + 1 如若不然，則對(duì)任一 i， 都有第 i 個(gè)巢中的鴿子數(shù)≤mi－1　則鴿子總數(shù)≤ m1 + m2 +… +mn－n ，與假設(shè)相矛盾．,容斥原理和鴿巢原理,推論１　n(m－1) + 1只鴿子進(jìn)n個(gè)巢，至少有一個(gè)巢內(nèi)至少有m只鴿子．,例　證明每個(gè)長(zhǎng)為n2+1的實(shí)數(shù)序列中，一定存在長(zhǎng)為n+1的遞增或遞減子序列（不一定是嚴(yán)格遞、減）。,推論２　若n個(gè)整數(shù)

22、的平均數(shù)大于r-1，則至少有一個(gè)整數(shù)大于等于r。,證明：設(shè),為任取的實(shí)數(shù)序列。若此序列中不存在長(zhǎng)為n+1的遞增子序列,則一定存在長(zhǎng)為n+1的遞減序列.,容斥原理和鴿巢原理,令mi為以ai為首項(xiàng)的最長(zhǎng)遞增子序列的長(zhǎng)度，i=1,2,…n2+1。,因?yàn)閚2+1=n[(n+1)-1]+1,由鴿籠原理的推論可知。,若有某個(gè)mi≥n+1，則結(jié)論成立。若不然，必有mi < n+1，從而有mi ≤ n。,容斥原理和鴿巢原理,應(yīng)用實(shí)例: 鎖具裝箱

23、問題某廠生產(chǎn)一種彈子鎖具, 每個(gè)鎖具的鑰匙有 5個(gè)槽, 每個(gè)槽的高度從{1, 2, 3, 4, 5, 6}6個(gè)數(shù)(單位略)中任取一數(shù). 由于工藝及其它原因, 制造鎖具時(shí)對(duì) 5 個(gè)槽的高度還有兩個(gè)限制：至少有3個(gè)不同的數(shù)；相鄰兩槽的高度之差不能為 5. 滿足以上條件制造出來的所有互不相同的鎖具稱為一批.,容斥原理和鴿巢原理,從顧客的利益出發(fā)，自然希望在每批鎖具中“一把鑰匙開一把鎖”. 但是在當(dāng)前工藝條件下，對(duì)于同一批中兩個(gè)鎖是否能夠互

24、開，有以下試驗(yàn)結(jié)果：若二者相對(duì)應(yīng)的5個(gè)槽的高度中有 4 個(gè)相同, 另一個(gè)槽的高度差為1, 則可能互開; 在其它情形下, 不可能互開.原來，銷售部門在一批鎖具中隨意的取60個(gè)裝一箱出售. 團(tuán)體顧客往往購(gòu)買幾箱到幾十箱, 他們抱怨購(gòu)得的鎖具會(huì)出現(xiàn)互開的情形. 現(xiàn)聘你為顧問, 回答并解決以下的問題：,容斥原理和鴿巢原理,1） 每一批鎖具有多少個(gè)，裝多少箱.2） 為銷售部門提出一種方案，包括如何裝箱（仍是 60 個(gè)鎖具一箱），如何給箱子以標(biāo)

25、志，出售時(shí)如何利用這些標(biāo)志，使團(tuán)體顧客不再或減少抱怨. 3） 采取你提出的方案，團(tuán)體顧客的購(gòu)買量不超過多少箱，就可以保證一定不會(huì)出現(xiàn)互開的情形. 4） 按照原來的裝箱辦法，如何定量地衡量團(tuán)體顧客抱怨互開的程度(試對(duì)購(gòu)買一、二箱者給出具體結(jié)果).,容斥原理和鴿巢原理,我們主要根據(jù)生產(chǎn)一批鎖具的三個(gè)條件，用排列組合的知識(shí)對(duì)一批鎖具的總數(shù)目進(jìn)行求解. 設(shè)h1, h2, h3, h4, h5分別表示相應(yīng)的槽高取值, 其主要過程如下：(1)

26、 鑰匙槽高度的可能排列有65=7776種.(2) 因?yàn)橹辽儆?個(gè)不同的數(shù), 相鄰兩槽的高度之差不能為 5的約束，實(shí)際制鎖時(shí)還要除去一部分鑰匙槽高度的排列方式，我們稱這些排列方式形成的集合為除去集D.(3) 相鄰兩槽的高度之差不能為5等價(jià)為鑰匙槽高度排列方式中不能出現(xiàn)1和6相鄰的情況.,容斥原理和鴿巢原理,(4) 對(duì)除去集D可進(jìn)行如下劃分： 令D1={h1= h2= h3= h4= h5的排列} D2={hi

27、(i = 1, 2, 3, 4, 5)中只有兩個(gè)不同數(shù)的排列}； D3={ hi (i = 1, 2, 3, 4, 5)中有三個(gè)不同數(shù)且1和6相鄰的排列} D4={ hi (i = 1, 2, 3, 4, 5)中有四個(gè)不同數(shù)且1和6相鄰的排列} D5={ hi (i = 1, 2, 3, 4, 5)各不相同且 1和 6相鄰的排列}；,顯然，Di (i = 1, 2, 3, 4, 5)是D的一個(gè)完

28、全劃分，即D1∪D2∪D3∪D4∪D5= D, 且Di∩Dj =f (i, j=1, 2, 3, 4, 5且i≠j).我們分別求出了Di (i = 1, 2, 3, 4, 5)中的元素個(gè)數(shù)如下：| D1|=6；| D2|=450；| D3|=456；| D4| =792；| D5|=192. 其中, |D|表示集合D中元素的個(gè)數(shù).綜上，一批鎖具的總數(shù)為 7776一（6＋456＋792＋192）= 5880件.可裝的箱數(shù)為58

29、80÷60=98箱.,容斥原理和鴿巢原理,例　設(shè)A= a1a2···a20是10個(gè)0和10個(gè)1 組成的２進(jìn)制數(shù)．B=b1b2···b20是任意的２進(jìn)制數(shù)．C = b1b2···b20 b1b2···b20 = C1C2···C40，則存在某個(gè)i ，1≤ i ≤20，使得C

30、iCi+1···Ci+19與a1a2···a20至少有10位對(duì)應(yīng)相等．,A,B,C,,,第 i 格,第 i +19格,1 2 ········· 19 20 1 2 ····

31、··· 19 20,1 2 ········　　　 19 20 1 ······ 19 20,容斥原理和鴿巢原理,證　在C = C1C2···C40中，當(dāng) i 遍歷