鴿巢原理 容斥原理

《鴿巢原理 容斥原理》由會員分享，可在線閱讀，更多相關(guān)《鴿巢原理 容斥原理（27頁珍藏版）》請在裝配圖網(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ù)的個數(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ù)學歸納法可獲得容斥原理的一般形式： 定理定理3 3 設(shè)12,.,nA AA是有限集合，則12111112|.|. ( 1)|.|nnnniijijkiij iij i kjnnAAAAAAAAAAAA 第5頁/共27頁7容斥原理 容斥原理的等價形式： 定理定理4 4 設(shè)12,.,nA AA是有限集合，則1211121|.| | . ( 1) |.|nnniijiij innijknij i kjAAAEAAAAAAAAA 第6頁/共27頁8容斥原理 例2 一個學校只有三門課程：數(shù)學、物理、

3、化學。已知修這三門課的學生分別有170、130、120人；同時修數(shù)學、物理兩門課的學生45人；同時修數(shù)學、化學的20人；同時修物理、化學的22人。同時修三門的3人。問這學校共有多少學生？ 解 令M、P、C分別為修數(shù)學、物理、化學的學生集合 則該問題轉(zhuǎn)化為求|MPC| |MPCMPCMPMCPCMPC170 130 1204520223336第7頁/共27頁9容斥原理 例3 求11000中不能被5、6和8中任何一數(shù)整除的整數(shù)的個數(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ù)的個數(shù)為 |ABC| =|E|-（A+B+C）+（AB+AC+BC）-ABC =600第9頁/共27頁11容斥原理 例4 求a,b,c,d,e,f六個字母的全排列中不出現(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ù)學中的應(yīng)用 錯排問題 有禁止模式的排列問題 第11頁/共27頁13錯排問題 錯排問題是指對n個元素依次給以標號1,2,n，求每個元素都不在自己原來位置上的排列數(shù)。 設(shè)Ai (i=1,2,n)為數(shù)i在第i位上的全體排列， 因數(shù)字i不能動，因而有|Ai|=(n-1)!，i=1,2,n 同理1212| (2)!, ,1,2,.,|.| ()!|.| 0!kijiiinAAni jnijAAAnkAAA 第12頁/共27頁14錯排問題

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

7、母的全排列中，令A1, 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中的每一個排列都可看作n-1元集合1, 2, i(i+1), n的一個全排列，所以|Ai|=(n-1)! 同理12121| (2)!|.| ()!|.| 1!k

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

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

11、1, a2, ,a100是由1和2組成的序列 ，已知從其中任一數(shù)開始的連續(xù)10個數(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項。 設(shè)39,39khkhSSkh SS即1.39hkaa第24頁/共27頁26思考題 從1到2n的正整數(shù)中任取n+1個數(shù)，則在這n+1個數(shù)中，至少有一對數(shù)，其中一個是另一個的倍數(shù)。證明:假設(shè)這n+1個數(shù)121,.,na aa令 2,1,2,.,1iiiar in,其中ri為奇數(shù)1,2 irn而,并且1,2n中只有n個奇數(shù)pqrrr因此必然存在 若 22pqpqarar 則 2ppar2qqar是 的倍數(shù) 第25頁/共27頁27課后練習題 1、在34的長方形內(nèi)任意放置7個點，在其中至少有兩個點的距離小于等于51/2。 第26頁/共27頁