組合數(shù)學(xué)(西安電子科技大學(xué)(第二版第四章容斥原理.ppt

第4章 容斥原理,引言 容斥原理 應(yīng)用 限制排列與棋盤多項式 莫比烏斯反演公式,4.1 引言,例 在一根長的木棍上有兩種刻度線，第一種刻度線將木棍分成10等份，第二種將木棍分成12等份。如果沿每條刻度線將木棍鋸斷，木棍總共被鋸成多少段？,4.1 引言,例 在一根長的木棍上有三種刻度線，第一種刻度線將木棍分成10等份，第二種將木棍分成12等份，第三種將木棍分成15等份。如果沿每條刻度線將木棍鋸斷，木棍總共被鋸成多少段？,4.1 引言,4.1 引言,4.1 引言,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.3 應(yīng)用,例 1與1000之間不能被4,5和6整除的整數(shù)有多少個？,解: 令A(yù)=1,2,3,1000，則 |A|=1000. 記A1、A2、A3分別為在1與1000之間能被4,5和6整除的整數(shù) 集合，則有： |A1| = L1000/4=250, |A2| = L1000/5=200, |A3| = L1000/6=166,4.3 應(yīng)用,于是A1A2 表示A中能被4和5整除的數(shù),即能被20整除的數(shù)，其個數(shù)為 |A1A2|=L1000/20=50； 同理, |A1A3|=L1000/12=83, |A2A3|=L1000/30=33,4.3 應(yīng)用,A1 A2 A3 表示A中能同時被4,5,6整除的數(shù)，即A中能被4,5,6的最小公倍數(shù)lcm(4,5,6)=60整除的數(shù)，其個數(shù)為 | A1A2A3|=L1000/60= 16. 由容斥原理知，A中不能被4,5,6整除的整數(shù)個數(shù)為:,4.3 應(yīng)用,例 六一兒童節(jié)快到了，有愛心巧手媽媽做了3個布娃娃、4個小布熊、5個布兔子共12個布玩具，現(xiàn)選10個送給某兒童福利院，如果忽略同類玩具的差異那么有多少種選送方法？,此問題相當于求S=3a,4b,5c的10-組合數(shù).,4.3 應(yīng)用,例 求S=3a,4b,5c的10-組合數(shù).,解: 令S=a, b,c，則S的10-組合數(shù)為,設(shè)集合A是S的10-組合全體，則|A|66，現(xiàn)在要求在10 組合中的a的個數(shù)小于等于3，b的個數(shù)小于等于4，c的個 數(shù)小于等于5的組合數(shù). 定義性質(zhì)集合P=P1,P2,P3,其中： P1：10組合中a的個數(shù)大于等于4； P2：10組合中b的個數(shù)大于等于5； P3：10組合中c的個數(shù)大于等于6. 將滿足性質(zhì)Pi的10-組合全體記為Ai(1i3).,4.3 應(yīng)用,那么，A1中的元素可以看作是由S的1046組合再拼上4個a構(gòu)成的，所以,同理，,類似地，,而a的個數(shù)小于等于3，b的個數(shù)小于等于4，c的個數(shù)小于等于5的10-組合全體為 由容斥原理知，它的元素個數(shù)為:,4.3 應(yīng)用,例 確定在非負整數(shù)x1,x2,x3,x4不大于7時，方程x1+x2+x3+x4=10的整數(shù)解的個數(shù)。,解 設(shè)S為該方程的整數(shù)解的非負整數(shù)解集合，|S|=286,令Pi是性質(zhì)xi=8(i=1,2,3,4),并令A(yù)i為S中具有性質(zhì)Pi的集合，問題變?yōu)榍?A1是方程x1+x2+x3+x4=10(x1=8,x2=0,x3=0,x3=0)的整數(shù)解集合。,類似地，,而Ai(i=1,2,3,4)的任意兩個以及兩個以上的交集均為空集，故,4.3 應(yīng)用,4.3 應(yīng)用,例 在一次聚會上有n為男士和n位女士。這n位女士能夠有多少種方法選擇男舞伴？如果每個人必須換舞伴，那么第二次跳舞又有多少種選擇方法？,4.3 應(yīng)用,證明：令S是1,2,n的全排列的全體，則|S|n!. 定義S上的性質(zhì)集合P=P1,P2,P3,.,Pn,其中Pi表示排列中i在其自然順序的位置上(1in).令A(yù)i為S中滿足性質(zhì)Pi的全排列的集合.,因Ai中的每一個全排列形如 j1ji-1iji+1jn， 而j1ji-1ji+1jn是1,2,i-1,i+1,n的全排列，所以有 |Ai|=(n-1)! (1in). 同理，有|AiAj|=(n-2)! (1ijn). 一般地，有 |Ai1Ai2Aik|=(n-k)!， 其中1i1,i2,ikn,且i1,i2,ik互不相等.,4.3 應(yīng)用,而Dn為S中不滿足性質(zhì)Pi的元素的個數(shù)，由容斥原理，有,4.3 應(yīng)用,例 確定1,2,3,4,5,6,7,8的沒有偶數(shù)在它的自然位置上的排列數(shù)。,例 確定1,2,n的恰有k個整數(shù)在它們的自然位置上的排列數(shù)。,4.3 應(yīng)用,4.3 應(yīng)用,4.3 應(yīng)用,4.3 應(yīng)用,4.3 應(yīng)用,4.3 應(yīng)用,4.3 應(yīng)用,4.3 應(yīng)用,4.4 限制排列與棋盤多項式,4.4 限制排列與棋盤多項式,4.4 限制排列與棋盤多項式,4.4 限制排列與棋盤多項式,例 8個小孩圍坐在旋轉(zhuǎn)木馬上，問有多少種變換座位的方法，使得每個小孩前面坐的都不是原來的小孩？,解 將圍坐在旋轉(zhuǎn)木馬上的8個小孩按逆時針方向用1,2,8編號,那么,問題就是在1,2,8的循環(huán)排列中沒有模式12,23,78,81的全體的數(shù)目。,設(shè)S是1,2,8的循環(huán)排列全體，則|S|=7!。,設(shè) A1=S中1和2連續(xù)排在一起的循環(huán)排列 A2=S中2和3連續(xù)排在一起的循環(huán)排列 A8=S中8和1連續(xù)排在一起的循環(huán)排列,則問題歸結(jié)為求,4.4 限制排列與棋盤多項式,(1) |Ai|=6!,i=1,2,8. (2) |AiAj|=5!. |Ai1Ai 2 Aik |=(8-k)!,所以，,4.4 限制排列與棋盤多項式,6.4、5 帶有禁止位置的排列,例求多重集S=3a, 4b, 2c的排列數(shù)，其中同一種字母的全體不得連續(xù)出現(xiàn)（例如，abbbbcaac是不允許的，而abbbacacb是允許的）。,4.4 限制排列與棋盤多項式,4.4 限制排列與棋盤多項