鴿巢原理 容斥原理

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

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

2、有限集合，則 | | | |ABCABCABACBCABC | ?ABC第4頁(yè)/共27頁(yè)6容斥原理 利用數(shù)學(xué)歸納法可獲得容斥原理的一般形式： 定理定理3 3 設(shè)12,.,nA AA是有限集合，則12111112|.|. ( 1)|.|nnnniijijkiij iij i kjnnAAAAAAAAAAAA 第5頁(yè)/共27頁(yè)7容斥原理 容斥原理的等價(jià)形式： 定理定理4 4 設(shè)12,.,nA AA是有限集合，則1211121|.| | . ( 1) |.|nnniijiij innijknij i kjAAAEAAAAAAAAA 第6頁(yè)/共27頁(yè)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人。問(wèn)這學(xué)校共有多少學(xué)生？ 解 令M、P、C分別為修數(shù)學(xué)、物理、化學(xué)的學(xué)生集合 則該問(wèn)題轉(zhuǎn)化為求|MPC| |MPCMPCMPMCPCMPC170 130 1204520223336第7頁(yè)/共27頁(yè)9容斥原理 例3 求11000中不能被5、6和8中任何一數(shù)整除的整數(shù)的個(gè)數(shù) 解：設(shè)11000之間的整數(shù)構(gòu)成全集E A、B、C分別表示其中可被5，6，8整除的數(shù)的集合 則問(wèn)題轉(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頁(yè)/共27頁(yè)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頁(yè)/共27頁(yè)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頁(yè)/共27頁(yè)12容斥原理在組合數(shù)學(xué)中的應(yīng)用 錯(cuò)排問(wèn)題 有禁止模式的排列問(wèn)題 第11頁(yè)/共27頁(yè)13錯(cuò)排問(wèn)題 錯(cuò)排問(wèn)題是指對(duì)n個(gè)元素依次給以標(biāo)號(hào)1,2,n，求每個(gè)元素都不在自己原來(lái)位置上的排列數(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頁(yè)/共27頁(yè)14錯(cuò)排問(wèn)題

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

7、母的全排列中，令A(yù)1, A2, A3, A4分別表示A, C, E, G在原來(lái)位置上的排列 則滿足要求的排列為 1234|44448!7!6!5!4!123424024AAAA 第15頁(yè)/共27頁(yè)17有禁止模式的排列問(wèn)題 有禁止模式的排列問(wèn)題主要解決某些元素之間的某種相對(duì)位置不能出現(xiàn)的一類排列。 下面我們僅討論有禁止模式的排列問(wèn)題中最簡(jiǎn)單的一種相鄰禁位問(wèn)題。第16頁(yè)/共27頁(yè)18相鄰禁位問(wèn)題 相鄰禁位問(wèn)題：求由集合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頁(yè)/共27頁(yè)19相鄰禁位問(wèn)題 設(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頁(yè)/共27頁(yè)20相鄰禁位問(wèn)題121111211111|.| | .( 1)|.|111 !(1)!(2)! .( 1)1!121nnnniijniij nnQAAASAAAAAAnnnnnnn 第19頁(yè)/共27頁(yè)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ù)在原來(lái)位置上，其余都不在原來(lái)位置的錯(cuò)排數(shù)目。第20頁(yè)/共27頁(yè)22鴿巢原理 第21頁(yè)/共27頁(yè)23鴿巢原理 鴿巢原理是組合數(shù)學(xué)中最簡(jiǎn)單也是

10、最基本的原理，也叫抽屜原理。 原理描述：若有n個(gè)鴿子巢，n+1只鴿子，則至少有一個(gè)鴿子巢里住著兩只鴿子。 定理（鴿巢原理） 如果把n+1個(gè)物體放入n個(gè)盒子，那么至少有一個(gè)盒子中有兩個(gè)或更多的物品。第22頁(yè)/共27頁(yè)24舉例 例1 367人中至少有2人的生日相同。 例2 在某班中有50名學(xué)生，其中年齡最大的20歲，最小的17歲。證明這個(gè)班中至少有兩名學(xué)生是同年同月生的。 例3 在邊長(zhǎng)為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頁(yè)/共27頁(yè)25舉例 例5 設(shè)a

11、1, a2, ,a100是由1和2組成的序列 ，已知從其中任一數(shù)開始的連續(xù)10個(gè)數(shù)的和不超過(guò)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頁(yè)/共27頁(yè)26思考題 從1到2n的正整數(shù)中任取n+1個(gè)數(shù)，則在這n+1個(gè)數(shù)中，至少有一對(duì)數(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頁(yè)/共27頁(yè)27課后練習(xí)題 1、在34的長(zhǎng)方形內(nèi)任意放置7個(gè)點(diǎn)，在其中至少有兩個(gè)點(diǎn)的距離小于等于51/2。 第26頁(yè)/共27頁(yè)