鴿巢原理 容斥原理

《鴿巢原理 容斥原理》由會(huì)員分享，可在線閱讀，更多相關(guān)《鴿巢原理 容斥原理（27頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、鴿巢原理 容斥原理2容斥原理 集合論加法法則： 若|A|=m，|B|=n，AB= ， 則|AB|=m+n。 思考：若A、B為任意的有限集合，則|AB|=？第1頁/共27頁3容斥原理| |ABABAB&定理定理1 1 若A、B為任意的有限集合，則 第2頁/共27頁4容斥原理 例1 求不超過20的正整數(shù)中是2的倍數(shù)或3的倍數(shù)的數(shù)的個(gè)數(shù)。 解：設(shè)A、B分別表示不超過20的正整數(shù)中2的倍數(shù)的數(shù)的集合和3的倍數(shù)的數(shù)的集合，則問題轉(zhuǎn)化為求|AB| 易見|A|=10，|B|=6，|AB |=3 因此|AB|=|A|+|B|- | AB |=13第3頁/共27頁5容斥原理&定理定理2 2 若A、B、C為任意的

2、有限集合，則 | | | |ABCABCABACBCABC | ?ABC第4頁/共27頁6容斥原理 利用數(shù)學(xué)歸納法可獲得容斥原理的一般形式： 定理定理3 3 設(shè)12,.,nA AA是有限集合，則12111112|.|. ( 1)|.|nnnniijijkiij iij i kjnnAAAAAAAAAAAA 第5頁/共27頁7容斥原理 容斥原理的等價(jià)形式： 定理定理4 4 設(shè)12,.,nA AA是有限集合，則1211121|.| | . ( 1) |.|nnniijiij innijknij i kjAAAEAAAAAAAAA 第6頁/共27頁8容斥原理 例2 一個(gè)學(xué)校只有三門課程：數(shù)學(xué)、物理、

3、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時(shí)修數(shù)學(xué)、化學(xué)的20人；同時(shí)修物理、化學(xué)的22人。同時(shí)修三門的3人。問這學(xué)校共有多少學(xué)生？ 解 令M、P、C分別為修數(shù)學(xué)、物理、化學(xué)的學(xué)生集合 則該問題轉(zhuǎn)化為求|MPC| |MPCMPCMPMCPCMPC170 130 1204520223336第7頁/共27頁9容斥原理 例3 求11000中不能被5、6和8中任何一數(shù)整除的整數(shù)的個(gè)數(shù) 解：設(shè)11000之間的整數(shù)構(gòu)成全集E A、B、C分別表示其中可被5，6，8整除的數(shù)的集合 則問題轉(zhuǎn)化為求|ABC| 由于ABC=1000/5，6，8=1000/120

4、=8 AB=1000/5，6=33 AC=1000/5，8=25 BC=1000/6，8=41 A=1000/5=200 B=1000/6=166 C=1000/8=125第8頁/共27頁10容斥原理 由ABC=8 AB=33 AC=25 BC=41 A=200 B=166 C=125 所以由容斥原理，不能被5，6和8整除的整數(shù)的個(gè)數(shù)為 |ABC| =|E|-（A+B+C）+（AB+AC+BC）-ABC =600第9頁/共27頁11容斥原理 例4 求a,b,c,d,e,f六個(gè)字母的全排列中不出現(xiàn)ace和df的排列數(shù)。 解 設(shè)E為全排列集合，A為出現(xiàn)ace的排列的集合，B為出現(xiàn)df的排列的集合，

5、 | 6!,| 4!,| 5!,| 3!EABAB則根據(jù)容斥原理，不出現(xiàn)ace和df的排列數(shù)為| 6! (5! 4!)3!582AB第10頁/共27頁12容斥原理在組合數(shù)學(xué)中的應(yīng)用 錯(cuò)排問題 有禁止模式的排列問題 第11頁/共27頁13錯(cuò)排問題 錯(cuò)排問題是指對n個(gè)元素依次給以標(biāo)號(hào)1,2,n，求每個(gè)元素都不在自己原來位置上的排列數(shù)。 設(shè)Ai (i=1,2,n)為數(shù)i在第i位上的全體排列， 因數(shù)字i不能動(dòng)，因而有|Ai|=(n-1)!，i=1,2,n 同理1212| (2)!, ,1,2,.,|.| ()!|.| 0!kijiiinAAni jnijAAAnkAAA 第12頁/共27頁14錯(cuò)排問題

6、 定理 用Dn表示1, 2, , n的全部錯(cuò)排個(gè)數(shù)，則12|.|!(1)!(2)! .( 1)0!12111!(1.( 1)1!2!nnnnDAAAnnnnnnnnn 第13頁/共27頁15錯(cuò)排問題 例 在8個(gè)字母ABCDEFGH的全排列中，求 （1）僅ACEG四個(gè)字母不在原來位置上的排列數(shù) （2）只有4個(gè)字母不在原來位置的排列數(shù) （3）ACEG四個(gè)字母不在原來上的排列數(shù) 解 （1）8個(gè)字母中僅ACEG四個(gè)字母不在原來位置上，其余4個(gè)字母保持不動(dòng)，相當(dāng)于4個(gè)元素的錯(cuò)排11114! (1)91!2!3!4!排列數(shù)為（2）排列數(shù)為C(8, 4)9=630第14頁/共27頁16錯(cuò)排問題 （3）8個(gè)字

7、母的全排列中，令A(yù)1, A2, A3, A4分別表示A, C, E, G在原來位置上的排列 則滿足要求的排列為 1234|44448!7!6!5!4!123424024AAAA 第15頁/共27頁17有禁止模式的排列問題 有禁止模式的排列問題主要解決某些元素之間的某種相對位置不能出現(xiàn)的一類排列。 下面我們僅討論有禁止模式的排列問題中最簡單的一種相鄰禁位問題。第16頁/共27頁18相鄰禁位問題 相鄰禁位問題：求由集合1, 2, , n產(chǎn)生的不出現(xiàn)12, 34, , n(n-1)的全排列數(shù) 設(shè)Qn表示1, 2, , n的不出現(xiàn)12, 34, , n(n-1)的全排列數(shù) 則Q1 =1，滿足要求的排列

8、為1； Q2 =1，滿足要求的排列為21； Q3 =3，滿足要求的排列為213, 321, 132； Q4 =11，滿足要求的排列為：4132, 3142, 2143，1324, 4213, 3214, 2413, 1432, 4321, 3241, 2431Qn =？第17頁/共27頁19相鄰禁位問題 設(shè)S為1, 2, n的所有全排列，則|S|=n!， 設(shè)Ai （i=1,2,n-1）表示全排列中出現(xiàn)i(i+1)模式的排列的集合 則Ai中的每一個(gè)排列都可看作n-1元集合1, 2, i(i+1), n的一個(gè)全排列，所以|Ai|=(n-1)! 同理12121| (2)!|.| ()!|.| 1!k

9、ijiiinAAnAAAnkAAA第18頁/共27頁20相鄰禁位問題121111211111|.| | .( 1)|.|111 !(1)!(2)! .( 1)1!121nnnniijniij nnQAAASAAAAAAnnnnnnn 第19頁/共27頁21課后練習(xí) （1）求1250之間能被2、3、5和7任何一數(shù)整除的整數(shù)個(gè)數(shù)。 （2）在由a、b、c和d這4個(gè)字符構(gòu)成的n位字符串中，求a、b、c至少出現(xiàn)一次的符號(hào)串的數(shù)目。 （3）數(shù)1，2，9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置的錯(cuò)排數(shù)目。第20頁/共27頁22鴿巢原理 第21頁/共27頁23鴿巢原理 鴿巢原理是組合數(shù)學(xué)中最簡單也是

10、最基本的原理，也叫抽屜原理。 原理描述：若有n個(gè)鴿子巢，n+1只鴿子，則至少有一個(gè)鴿子巢里住著兩只鴿子。 定理（鴿巢原理） 如果把n+1個(gè)物體放入n個(gè)盒子，那么至少有一個(gè)盒子中有兩個(gè)或更多的物品。第22頁/共27頁24舉例 例1 367人中至少有2人的生日相同。 例2 在某班中有50名學(xué)生，其中年齡最大的20歲，最小的17歲。證明這個(gè)班中至少有兩名學(xué)生是同年同月生的。 例3 在邊長為2的等邊三角形內(nèi)任意放置5個(gè)點(diǎn)，則其中至少有兩個(gè)點(diǎn)的距離小于1。 例4 某次會(huì)議有n位代表參加，每位代表至少認(rèn)識(shí)其余n-1位中的一位，則這n位代表中，至少有兩位認(rèn)識(shí)的人數(shù)相等。第23頁/共27頁25舉例 例5 設(shè)a

11、1, a2, ,a100是由1和2組成的序列 ，已知從其中任一數(shù)開始的連續(xù)10個(gè)數(shù)的和不超過16，即ai+ai+1+ai+916 (1i91)，則存在h和k (kh)，使得ah+1+ah+2+ak=39。 證明： 11,2,.,100jjiiSaj，設(shè)12100.SSS顯然100110112091100(.)(.).(.)Saaaaaa根據(jù)題義有10010 16160S 作序列121001100,.,39,.,39S SSSS，共200項(xiàng)。 設(shè)39,39khkhSSkh SS即1.39hkaa第24頁/共27頁26思考題 從1到2n的正整數(shù)中任取n+1個(gè)數(shù)，則在這n+1個(gè)數(shù)中，至少有一對數(shù)，其中一個(gè)是另一個(gè)的倍數(shù)。證明:假設(shè)這n+1個(gè)數(shù)121,.,na aa令 2,1,2,.,1iiiar in,其中ri為奇數(shù)1,2 irn而,并且1,2n中只有n個(gè)奇數(shù)pqrrr因此必然存在 若 22pqpqarar 則 2ppar2qqar是 的倍數(shù) 第25頁/共27頁27課后練習(xí)題 1、在34的長方形內(nèi)任意放置7個(gè)點(diǎn)，在其中至少有兩個(gè)點(diǎn)的距離小于等于51/2。 第26頁/共27頁