鴿巢原理+容斥原理

1、1容斥原理 容斥原理（相容排斥原理）是組合計(jì)數(shù)中常用到的一種方法。 例1 求不超過20的正整數(shù)中是2的倍數(shù)或3的倍數(shù)的數(shù)的個(gè)數(shù)。 不超過20的正整數(shù)中是2的倍數(shù)的數(shù)有10個(gè)，即2, 4, 6, 8, 10, 12, 14, 16, 18, 20。不超過20的正整數(shù)中是3的倍數(shù)的數(shù)有6個(gè)，即3, 6, 9, 12, 15, 18。 但是不超過20的正整數(shù)中是2的倍數(shù)或3的倍數(shù)的數(shù)的個(gè)數(shù)不是10+6=16個(gè)，而是13個(gè)，因?yàn)槠渲?, 12, 18這三個(gè)數(shù)既是2的倍數(shù)又是3的倍數(shù)。2容斥原理集合論加法法則： 若|A|=m，|B|=n，AB= ， 則|AB|=m+n。思考：若A、B為任意的有限集合，則

2、|AB|=？3容斥原理定理1 若A、B為任意的有限集合，則 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 |=135容斥原理定理2 若A、B、C為任意的有限集合，則 6容斥原理利用數(shù)學(xué)歸納法可獲得容斥原理的一般形式： 定理3 設(shè)是有限集合，則7容斥原理容斥原理的等價(jià)形式： 定理4 設(shè)是有限集合，則8容斥原理例2 一個(gè)學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有17

3、0、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|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=8 AB=1000/5，6=33 AC=1000/5，8=25 BC=1000/6，8=41 A=1000/5=200 B=1000

4、/6=166 C=1000/8=12510容斥原理 由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 =60011容斥原理例4 求a,b,c,d,e,f六個(gè)字母的全排列中不出現(xiàn)ace和df的排列數(shù)。解 設(shè)E為全排列集合，A為出現(xiàn)ace的排列的集合，B為出現(xiàn)df的排列的集合， 則根據(jù)容斥原理，不出現(xiàn)ace和df的排列數(shù)為12容斥原理在組合數(shù)學(xué)中的應(yīng)用錯(cuò)排問題有禁止模式的排列問題 13錯(cuò)排問題 錯(cuò)排問題是指對(duì)n個(gè)元素依次給以標(biāo)號(hào)1,2,n，求每

5、個(gè)元素都不在自己原來位置上的排列數(shù)。 設(shè)Ai (i=1,2,n)為數(shù)i在第i位上的全體排列， 因數(shù)字i不能動(dòng)，因而有|Ai|=(n-1)!，i=1,2,n 同理14錯(cuò)排問題 定理 用Dn表示1, 2, , n的全部錯(cuò)排個(gè)數(shù)，則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ò)排排列數(shù)為（2）排列數(shù)為C(8, 4)9=63016錯(cuò)排問題 （3）8個(gè)字母的全排列中，令

6、A1, A2, A3, A4分別表示A, C, E, G在原來位置上的排列 則滿足要求的排列為 17有禁止模式的排列問題 有禁止模式的排列問題主要解決某些元素之間的某種相對(duì)位置不能出現(xiàn)的一類排列。 下面我們僅討論有禁止模式的排列問題中最簡單的一種相鄰禁位問題。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，滿足要求的排列為1； Q2 =1，滿足要求的排列為21； Q3 =3，滿足要求的排列為213, 321, 132； Q4 =11，滿

7、足要求的排列為：4132, 3142, 2143，1324, 4213, 3214, 2413, 1432, 4321, 3241, 2431Qn =？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)! 同理20相鄰禁位問題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ù)目

8、。 （3）數(shù)1，2，9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置的錯(cuò)排數(shù)目。22鴿巢原理 23鴿巢原理 鴿巢原理是組合數(shù)學(xué)中最簡單也是最基本的原理，也叫抽屜原理。 原理描述：若有n個(gè)鴿子巢，n+1只鴿子，則至少有一個(gè)鴿子巢里住著兩只鴿子。 定理（鴿巢原理） 如果把n+1個(gè)物體放入n個(gè)盒子，那么至少有一個(gè)盒子中有兩個(gè)或更多的物品。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ù)相等。25舉例 例5 設(shè)a1, 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。 證明： 設(shè)顯然根據(jù)題義有作序列，共200項(xiàng)。 設(shè)即26思考題 從1到2n的正整數(shù)中任取n+