組合數(shù)學第二講

1、容斥原理和鴿巢原理,§1 容斥原理,例 求[1，20]中2或3的倍數(shù)的個數(shù)。,[解] 2的倍數(shù)是：2,4,6,8,10,12,14,16,18,20. ←(10個)3的倍數(shù)是：3，6，9，12，15， 18。 ← (6個)但答案不是10+6=16 個，因為6，12，18在兩類中重復計數(shù)，應減去。故答案是：16-3=13,容斥原理和鴿巢原理,容斥原理研究有限集合的交或并的計數(shù)。,[DeMor

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

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

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

5、： 令 A為從1到500的整數(shù)中被3除盡的數(shù)的集合， B為被5除盡的數(shù)的集合,則,容斥原理和鴿巢原理,例3 求由a,b,c,d四個字母構成的n位符號串中，a,b,c至少出現(xiàn)一次的符號串數(shù)目。,解：令A、B、C分別為n位符號串中不出現(xiàn)a，b，c符號的集合。 由于n位符號串中每一位都可取a，b，c，d四種符號中的一個，故不允許出現(xiàn)a的n位符號串的個數(shù)應是：3n。,容斥原理和鴿巢原理,a，b，c

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

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

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

9、#215;1!) =280；,1. 有限制排列,容斥原理和鴿巢原理,同時有： |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； 全排列的個數(shù)為: 9!/(4! ×

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

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

12、上面定義下，顯然有　　rk(C)=rk－1(Ci)＋rk(Ce)，,容斥原理和鴿巢原理,即對任一指定的格子，要么布子，所得的方案數(shù)為 rk－1(Ci)；　要么不布子，方案數(shù)為 rk(Ce)。,設C有n個格子，則 r1(C)＝n．r1(C)＝r0(Ci) + r1(Ce)，∵　r1(Ce)＝n－1∴ r0(Ci)＝1．故規(guī)定 r0(C)＝1是合理的．,容斥原理和鴿巢原理,對任一指定的格子，要么布子，所得的方案數(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),容斥原理和鴿巢原理,利用前面的式子，可以把一個比較復雜的棋盤逐步分解成相對比較簡單的棋盤，從而得到其棋盤多項式。,容斥原理和鴿巢原理,３．有禁區(qū)

14、的排列,例 設對于排列P=P1 P2 P3 P4, 規(guī)定P1≠３,P２≠１、４， P３≠2、４， P4≠2。,這樣的排列對應于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。,容斥原理和鴿巢原理,定理　設 ri 為 i個棋子布入禁區(qū)的方案數(shù)，i =1,2,3,···,n。有禁區(qū)的布子方案數(shù)（即禁區(qū)內(nèi)不布子的方案數(shù)）為,例　１,２,３,４四位工人，A, B, C, D四項任務。條件如下：１不干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ù)學中最簡單也是最基本的原理，也叫抽屜原理。即,“若有n個鴿子巢，n+1個鴿子，則至少有一個巢內(nèi)有至少有兩個鴿子?！?例

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

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

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

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

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

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

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

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

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

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

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

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)中的元素個數(shù)如下：| D1|=6；| D2|=450；| D3|=456；| D4| =792；| D5|=192. 其中, |D|表示集合D中元素的個數(shù).綜上，一批鎖具的總數(shù)為 7776一（6＋456＋792＋192）= 5880件.可裝的箱數(shù)為58

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

30、iCi+1···Ci+19與a1a2···a20至少有10位對應相等．,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中，當 i 遍歷