第04講 計數(shù)問題-容斥原理與鴿籠原理

1、離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程離離 散散 數(shù)數(shù) 學(xué)學(xué)電子科技大學(xué)電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院計算機(jī)科學(xué)與工程學(xué)院信息與軟件工程學(xué)院信息與軟件工程學(xué)院20222022年年3 3月月7 7日星期一日星期一24-24-2 2離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-72.42.4 容斥原理與鴿籠原理容斥原理與鴿籠原理容斥原理容斥原理是研究若干有限集合交與并的計數(shù)問題是研究若干有限集合交與并的計數(shù)問題鴿籠原理鴿籠原理則是研究某些特定對象的存在

2、性問題。則是研究某些特定對象的存在性問題。 24-24-3 3離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-72.4.1 2.4.1 容斥原理容斥原理定義定義2.4.12.4.1 所謂所謂容斥容斥，是指我們計算某類物體的，是指我們計算某類物體的數(shù)目時，要排斥那些不應(yīng)包含在這個計數(shù)中的數(shù)目，數(shù)目時，要排斥那些不應(yīng)包含在這個計數(shù)中的數(shù)目，但同時要包容那些被錯誤地排斥了的數(shù)目，以此補但同時要包容那些被錯誤地排斥了的數(shù)目，以此補償。這種原理稱為償。這種原理稱為容斥原理容斥原理(The Principle of (The

3、 Principle of Inclusion-exclusion)Inclusion-exclusion)，又稱為，又稱為包含排斥原理包含排斥原理。24-24-4 4離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7定理定理2.4.12.4.1 設(shè)設(shè)A A和和B B是任意有限集合，有是任意有限集合，有|AB| = |A|AB| = |A|B|B|AB|AB|。分析分析 由圖容易看出，由圖容易看出，AB = (A - B)(AB)(B - A)AB = (A - B)(AB)(B - A)，A = ( A - B

4、)(AB)A = ( A - B)(AB)B = (AB)(B - A)B = (AB)(B - A)UA BABABA-BA-BB-AB-A|A| = |A-B|+|AB|B| = |AB|+|B-A|AB| = |A-B|+|AB|+|B-A| 推論推論2.4.22.4.2 設(shè)設(shè)U U為全集，為全集，A A和和B B是任意有限集合，則是任意有限集合，則ABU(AB)AB24-24-5 5離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.12.4.1對所給的集合驗證定理對所給的集合驗證定理2.4.1

5、2.4.1。（1 1）A = 1,2,3,4A = 1,2,3,4，B = 2,3,5,6,8B = 2,3,5,6,8；（2 2）A = 1,2,3,4A = 1,2,3,4，B = 5,6,7,8B = 5,6,7,8。 根據(jù)定理根據(jù)定理2.4.12.4.1，需先計算需先計算A AB B和和A AB B，再計算再計算|A|,|B|A|,|B|和和|A|AB|B|，然后代入公式然后代入公式(2.4.1)(2.4.1)兩端，驗證兩端，驗證等式即可。等式即可。分析分析解解 (1)(1) A AB=1,2,3,4,5,6,8B=1,2,3,4,5,6,8，A AB=2,3B=2,3 | A| A

6、B | = 7 , | AB | = 7 , | A B | = 2B | = 2 。 又又 |A|=4, |B|=5|A|=4, |B|=5， |A|A|B|B|AB|=4|AB|=45 52=7= |A2=7= |AB|B|即即定理定理2.4.12.4.1成立；成立； (2) (2)略。略。24-24-6 6離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7三個集合的情形三個集合的情形 定理定理2.4.32.4.3 設(shè)設(shè)A A，B B和和C C是任意三個有限集合，有是任意三個有限集合，有推論推論2.4.42.

7、4.4 設(shè)設(shè)U U為全集，為全集， A A，B B和和C C是任意有限集合，是任意有限集合，則則AABBC =( A + B + C)-( AC =( A + B + C)-( AB + AB + AC + BC + BC)+ AC)+ ABBC CAABBC = U -( A + B + C)C = U -( A + B + C)+( A+( AB + AB + AC + BC + BC)- AC)- ABBC C24-24-7 7離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.22.4.2 調(diào)查

8、調(diào)查260260個大學(xué)生，獲得如下數(shù)據(jù)：個大學(xué)生，獲得如下數(shù)據(jù)：6464人選修人選修數(shù)學(xué)課程，數(shù)學(xué)課程，9494人選修計算機(jī)課程，人選修計算機(jī)課程，5858人選修商貿(mào)課人選修商貿(mào)課程，程，2828人同時選修數(shù)學(xué)課程和商貿(mào)課程，人同時選修數(shù)學(xué)課程和商貿(mào)課程，2626人同時人同時選修數(shù)學(xué)課程和計算機(jī)課程，選修數(shù)學(xué)課程和計算機(jī)課程，2222人同時選修計算機(jī)人同時選修計算機(jī)課程和商貿(mào)課程，課程和商貿(mào)課程，1414人對三種課程都選修。問人對三種課程都選修。問（1 1）調(diào)查中）調(diào)查中三種課程都不選的學(xué)生三種課程都不選的學(xué)生有多少？有多少？（2 2）調(diào)查中）調(diào)查中只選修計算機(jī)科學(xué)課程的學(xué)生只選修計算機(jī)科學(xué)課

9、程的學(xué)生有多少？有多少？24-24-8 8離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.2 2.4.2 解解 設(shè)設(shè)A A、B B、C C分別表示選修數(shù)學(xué)課程，計算機(jī)課程分別表示選修數(shù)學(xué)課程，計算機(jī)課程和商貿(mào)課程的人構(gòu)成的集合，和商貿(mào)課程的人構(gòu)成的集合，則三種課程都不選的學(xué)生集合為則三種課程都不選的學(xué)生集合為 ，只選修計算機(jī)科學(xué)課程學(xué)生的集合為只選修計算機(jī)科學(xué)課程學(xué)生的集合為 。 UABCAABBC CAABBC C24-24-9 9離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國

10、家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.2 2.4.2 解（續(xù)）解（續(xù)）（1 1）|U|=260, |A|=64, |B|=94, |C|=58,|U|=260, |A|=64, |B|=94, |C|=58,| A AC|=28 ,|AC|=28 ,|AB|=26 ,|BB|=26 ,|BC|=22,C|=22, |A |AB B C|=14 C|=14，所以利用，所以利用容斥原理容斥原理得得 =106=106（2 2）A A B BC C = = U U- -( (A A + +B B+ + C C) )+ +( (A A B B+ + A AC C+

11、 +B BC C) )- -A A B BC CAABBC = B - AC = B - AB - BB - BC + AC + ABBC C= 94 -26-22+14= 60= 94 -26-22+14= 6024-24-1010離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7容斥原理的推廣容斥原理的推廣定理定理2.4.52.4.5 設(shè)設(shè)A A1 1, A, A2 2, , , A, An n是任意是任意n n個有限集合，個有限集合，則則推論推論2.4.62.4.6 設(shè)設(shè)U U為全集，為全集，A A1 1,

12、 A, A2 2, , , A, An n是任意是任意n n個個有限集合，則有限集合，則n n12niijijk12niijijki=1ii=1ijijijjk kn+1n+112n12nA A A A A=A -A A=A -A A +A A +A A A A A+(-1)A +(-1)A A A LLA 。A 。m m12niijijk12niijijki=1ii=1ijijijjk kn n12n12nA A A A A= U -A +A A= U -A +A A -A A -A A A A A+(-1) A +(-1) A A A A 。A 。24-24-1111離散數(shù)學(xué)課程組離散數(shù)學(xué)

13、課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.32.4.3 對對2424名科技人員進(jìn)行掌握外語情況的調(diào)查，其名科技人員進(jìn)行掌握外語情況的調(diào)查，其統(tǒng)計資料如下：會英、日、德、法語的人數(shù)分別為統(tǒng)計資料如下：會英、日、德、法語的人數(shù)分別為1313、5 5、1010和和9 9。其中同時會英語、日語的人數(shù)為。其中同時會英語、日語的人數(shù)為2 2；同時會英語和德語、同時會英語和法語、同時會德同時會英語和德語、同時會英語和法語、同時會德語和法語兩種語言的人數(shù)均為語和法語兩種語言的人數(shù)均為4 4；會日語的人既不；會日語的人既不會法語也不

14、會德語。試求會法語也不會德語。試求(1)(1)只會一種語言的人數(shù)各為多少？只會一種語言的人數(shù)各為多少？(2)(2)同時會英、德、法語的人數(shù)為多少？同時會英、德、法語的人數(shù)為多少？24-24-1212離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7解解設(shè)設(shè)A A、B B、C C、D D分別為會英、日、德、法語的人的集分別為會英、日、德、法語的人的集合，由已知條件可知：合，由已知條件可知：|A|A|1313，|B|B|5 5，|C|C|1010，|D|D|9 9，|AB|AB|2 2，|AC|AC|AD|AD|CD

15、|CD|4 4，|BC|BC|BD|BD|0,0,|ABC|ABC|ABD|ABD|BCD|BCD|0 0，|ABCD|ABCD|0 0，|ABCD|ABCD|2424，24-24-1313離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7解（續(xù)）解（續(xù)） 利用利用容斥原理容斥原理，并代入已知條件得，并代入已知條件得 24 2413135 510109 92 24 44 44 40 00 0 0 00 00 0|ACD|ACD|0 0。得：得：|ACD|ACD|1 1，即同時會英、德、法語的只有，即同時會英、德、

16、法語的只有1 1人。人。24-24-1414離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.3 2.4.3 解（續(xù)）解（續(xù)）設(shè)設(shè)只會英、日、德、法語的人數(shù)分別為只會英、日、德、法語的人數(shù)分別為x x1 1,x,x2 2,x,x3 3,x,x4 4，則則 x x1 1|A|A|(BCD)A|(BCD)A| |A|A|(BA)(CA)(DA)|(BA)(CA)(DA)|對對BABA、CACA、DADA應(yīng)用應(yīng)用容斥原理容斥原理，得，得 |(BA)(CA)(DA)| |(BA)(CA)(DA)| 2 24

17、44 40 00 01 10 09 9故，故，x x1 113-913-94 4。類似地類似地可求出：可求出：x x2 23 3，x x3 33 3，x x4 42 2。24-24-1515離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-72.4.2 2.4.2 鴿籠原理鴿籠原理 鴿籠原理（鴿籠原理（Pigeonhole PrinciplePigeonhole Principle）又稱為抽屜）又稱為抽屜原理、鴿舍原理，是指如下定理。原理、鴿舍原理，是指如下定理。定理定理2.4.7(2.4.7(鴿籠原理鴿籠原理)

18、) 若有若有n+1n+1只鴿子住進(jìn)只鴿子住進(jìn)n n個鴿籠，個鴿籠，則則鴿籠鴿籠2 2只鴿子。只鴿子。證明證明( (反證法反證法) ) 假設(shè)每個鴿籠至多住進(jìn)假設(shè)每個鴿籠至多住進(jìn)1 1只鴿子，則只鴿子，則n n個鴿籠至多住進(jìn)個鴿籠至多住進(jìn)n n只鴿子，這與有只鴿子，這與有n+1n+1只鴿子矛盾。只鴿子矛盾。故存在一個鴿籠至少住進(jìn)故存在一個鴿籠至少住進(jìn)2 2只鴿子。只鴿子。 注意：注意：（1 1）鴿籠原理僅提供了）鴿籠原理僅提供了存在性證明存在性證明；（2 2）使用鴿籠原理，必須能夠）使用鴿籠原理，必須能夠正確識別鴿子正確識別鴿子( (對象對象) )和和鴿巢鴿巢( (某類要求的特征某類要求的特征)

19、)，并且能夠計算出鴿子數(shù)和，并且能夠計算出鴿子數(shù)和鴿巢數(shù)。鴿巢數(shù)。24-24-1616離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.42.4.4抽屜里有抽屜里有3 3雙手套，問從中至少取多少只，雙手套，問從中至少取多少只，才能保證配成一雙？才能保證配成一雙？分析：分析：將手套看成是鴿子，將手套看成是鴿子，3 3雙手套的數(shù)量雙手套的數(shù)量3 3看成是看成是3 3個鴿巢，按照同型手套飛入同一個個鴿巢，按照同型手套飛入同一個籠子的原則，根據(jù)鴿籠原理，需要籠子的原則，根據(jù)鴿籠原理，需要4 4只手套只手套即可

20、。即可。答：答：4 4只。只。24-24-1717離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.52.4.5 設(shè)設(shè)1 1到到1010中任意選出六個數(shù)，那么其中有兩個數(shù)中任意選出六個數(shù)，那么其中有兩個數(shù)的和是的和是1111。證明證明 (1)(1)構(gòu)造構(gòu)造5 5個鴿籠：個鴿籠： A A1 1=1,10=1,10，A A2 2=2,9=2,9，A A3 3=3,8=3,8， A A4 4=4,7=4,7，A A5 5=5,6=5,6 (2)(2)選出的選出的6 6個數(shù)為鴿子個數(shù)為鴿子. . 根據(jù)根據(jù)鴿籠

21、原理鴿籠原理，所選出的，所選出的6 6個數(shù)中一定有兩個個數(shù)中一定有兩個數(shù)屬于同一個集合，這兩個數(shù)的和為數(shù)屬于同一個集合，這兩個數(shù)的和為1111。24-24-1818離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7定理定理2.4.52.4.5若有若有n n只鴿子住進(jìn)只鴿子住進(jìn)m m（m mn n）個鴿籠，則）個鴿籠，則存在一個存在一個鴿籠鴿籠至少住至少住進(jìn)進(jìn) 只鴿子。這里，只鴿子。這里， 表示小于等于表示小于等于x x的最大整數(shù)。的最大整數(shù)。n -1n -1+1+1m mx x24-24-1919離散數(shù)學(xué)課程組離

22、散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-7例例2.4.62.4.6如果一個圖書館里如果一個圖書館里3030本離散數(shù)學(xué)書共有本離散數(shù)學(xué)書共有12031203頁，那頁，那么必然有一本離散數(shù)學(xué)書至少有么必然有一本離散數(shù)學(xué)書至少有4141頁。頁。證明證明 設(shè)頁是鴿子，離散數(shù)學(xué)書是鴿籠，把每頁分設(shè)頁是鴿子，離散數(shù)學(xué)書是鴿籠，把每頁分配到它所出現(xiàn)的離散數(shù)學(xué)書中，根據(jù)定理配到它所出現(xiàn)的離散數(shù)學(xué)書中，根據(jù)定理2.4.52.4.5，則存在一個鴿籠至少住進(jìn)則存在一個鴿籠至少住進(jìn) = 41= 41，即結(jié)論得證。即結(jié)論得證。(1203 -1)/30 +1(1203 -1)/30 +124-24-2020離散數(shù)學(xué)課程組離散數(shù)學(xué)課程組國家級精品課程，國家雙語教學(xué)示范課程國家級精品課程，國家雙語教學(xué)示范課程2022-3-72022-3-72.52.5 離散概率簡介離散概率簡介 概率概率(Probability)(Probability)是是1717世紀(jì)為分析博弈游戲世紀(jì)為分析博弈游戲而發(fā)展起來的學(xué)科，最初計算概率僅有計數(shù)一種方而發(fā)展起來的學(xué)科，最初計算概率僅有計數(shù)一種方法。法。 本節(jié)主要介紹離散概率的基本概率、基本性質(zhì)本節(jié)主要介紹離散概率的基本概率、基本