組合數(shù)學(xué)(3)省公開課一等獎(jiǎng)全國示范課微課金獎(jiǎng)?wù)n件

第六章容斥原理及應(yīng)用劉貴全gqliu@第1頁§6.1容斥原理例[1，20]中2或3倍數(shù)個(gè)數(shù)解2倍數(shù)是：2，4，6，8，10，12，14，16，18，20。10個(gè)3倍數(shù)是：3，6，9，12，15，18。6個(gè)但答案不是10+6=16個(gè)，因?yàn)?，12，18在兩類中重復(fù)計(jì)數(shù)，應(yīng)減去。故答案是：16-3=13第2頁

容斥原理研究有限集合交或并計(jì)數(shù)。[DeMorgan定理]論域U，補(bǔ)集(a)(b)§6.1容斥原理第3頁§6.1容斥原理DeMogan定理推廣：設(shè)A1,A2,…,An是U子集，則

(1)

(2)第4頁

設(shè)S為物品有窮集，P1和P2為兩種性質(zhì)，S中每個(gè)物品能夠含有或不含有這些性質(zhì)，A1和A2分別是含有性質(zhì)P1和P2物品組成子集。則既不含有性質(zhì)P1也不含有性質(zhì)P2物品子集大小為：其正確性能夠這么證實(shí)：每個(gè)既不含有性質(zhì)P1也不含有性質(zhì)P2物品對(duì)等式右邊貢獻(xiàn)凈值為1；其它物品對(duì)等式右邊貢獻(xiàn)凈值為0.§6.1容斥原理第5頁§6.1容斥原理SA2A1A1

A2第6頁

一樣有(1)定理：§6.1容斥原理第7頁

定理：(2)§6.1容斥原理第8頁§6.1容斥原理第9頁

§6.1容斥原理例一個(gè)學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門課學(xué)生45人；同時(shí)修數(shù)學(xué)、化學(xué)20人；同時(shí)修物理化學(xué)22人。同時(shí)修三門3人。問這學(xué)校共有多少學(xué)生？解令：M為修數(shù)學(xué)學(xué)生集合；

P為修物理學(xué)生集合；

C為修化學(xué)學(xué)生集合；第10頁§6.1容斥原理

|MP

C|=|M|+|P|+|C|-|MP|-|MC|-|PC|+|MPC|=170+130+120-45-20-22+3=336即學(xué)校學(xué)生數(shù)為336人。第11頁

設(shè)P1,P2,…,Pm為m種性質(zhì)，S中每個(gè)物品能夠含有或不含有這些性質(zhì)，設(shè)Ai={x:x∈S且x含有性質(zhì)Pi}，i=1,2,…,m定理6.1.1

S中不含有P1,P2,…,Pm中任何一個(gè)性質(zhì)物品個(gè)數(shù)為其中第一個(gè)Σ是對(duì){1,2,…,m}全部1-組合{i}求和；第二個(gè)Σ是對(duì){1,2,…,m}全部2-組合{i,j}求和；第三個(gè)Σ是對(duì){1,2,…,m}}全部3-組合{i,j,k}求和；......，如這類推?！?.1容斥原理第12頁證每個(gè)不含有P1,P2,…,Pm中任何一個(gè)性質(zhì)物品對(duì)等式右邊貢獻(xiàn)凈值為

1-0+0-…+(-1)m0=1每個(gè)含有P1,P2,…,Pm中任何n種(1≤n≤m)性質(zhì)物品對(duì)等式右邊貢獻(xiàn)凈值為C(n,0)-C(n,1)+C(n,2)-…+(-1)mC(n,n)=(1-1)n=0§6.1容斥原理第13頁推論6.1.2

S中含有P1,P2,…,Pm中最少一種性質(zhì)物品個(gè)數(shù)為|A1∪A2∪…∪Am|=Σ|Ai|-Σ|Ai∩Aj|+Σ|Ai∩Aj∩Ak|+…-(-1)mΣ|Ai∩Aj∩…∩Am|

若容斥原理中集合Ai1∩Ai2∩…∩Aik大小只依賴于k大小，不依賴于集合中有哪些元素，即存在常數(shù)α0,α1,…,αm使得§6.1容斥原理第14頁

0=|S|=|S|，

1=|A1|=|A2|=…=|Am|，2=|A1∩A2|=|A1∩A3|=……=|Am-1∩Am|…m=|A1∩A2∩…∩Am|,則容斥原理簡(jiǎn)化為=

0-C(m,1)

1+C(m,2)

2-…+(-1)kC(m,k)

k

+……+(-1)m

m

§6.1容斥原理第15頁例求a,b,c,d,e,f六個(gè)字母全排列中不允許出現(xiàn)ace和df圖像排列數(shù)。解：設(shè)A為ace作為一個(gè)元素出現(xiàn)排列集，B為df作為一個(gè)元素出現(xiàn)排列集，A

B為同時(shí)出現(xiàn)ace、df排列數(shù)。|A|=4!,|B|=5!,|A∩B|=3!依據(jù)容斥原理，不出現(xiàn)ace和df排列數(shù)為：=6!-(5!+4!)+3!=582§6.1容斥原理第16頁例

求從1到500整數(shù)中能被3或5除盡數(shù)個(gè)數(shù)。解：令A(yù)為從1到500整數(shù)中被3除盡數(shù)集合，B為被5除盡數(shù)集合則§6.1容斥原理被3或5除盡數(shù)個(gè)數(shù)為|AUB|=|A|+|B|-|A

B|=166+100?33=233第17頁例求由a、b、c、d四個(gè)字母組成n位符號(hào)串中，a、b、c皆最少出現(xiàn)一次符號(hào)串?dāng)?shù)目。解令A(yù)、B、C分別為n位符號(hào)串中不出現(xiàn)a，b，c符號(hào)集合。因?yàn)閚位符號(hào)串中每一位都可取a，b，c，d四種符號(hào)中一個(gè)，故不允許出現(xiàn)an位符號(hào)串個(gè)數(shù)應(yīng)是3n，即

|A|=|B|=|C|=3n|AB|=|B

C|=|C

A|=2n

|ABC

|=1§6.1容斥原理第18頁a，b，c最少出現(xiàn)一次n位符號(hào)串集合即為=4n-(|A|+|B|+|C|)+(|AB|+|B

C|+|C

A|)-|ABC|=4n-3·3n+3·2n-1§6.1容斥原理第19頁例用26個(gè)英文字母作不允許重復(fù)全排列，要求排除dog，god，gum，depth，thing字樣出現(xiàn)，求滿足這些條件排列數(shù)?！?.1容斥原理第20頁解：全部排列中，令：A1為出現(xiàn)dog排列全體；A2為出現(xiàn)god排列全體；A3為出現(xiàn)gum排列全體；A4為出現(xiàn)depth排列全體；A5為出現(xiàn)thing排列全體；§6.1容斥原理第21頁出現(xiàn)dog字樣排列，相當(dāng)于把dog作為一個(gè)單元參加排列，故|A1|=24!類似有：|A2|=|A3|=24!，|A4|=|A5|=

22!

因?yàn)間od,dog不可能在一個(gè)排列中同時(shí)出現(xiàn)，故：

|A1A2|=0

類似地：|A2A3|=0，|A1A4|=0§6.1容斥原理第22頁因?yàn)間um,dog能夠在dogum字樣中同時(shí)出現(xiàn)，故有：|A1

A3|=22!類似有g(shù)od和depth能夠在godepth字樣中同時(shí)出現(xiàn)，故|A2

A4|=20!god和thing能夠在thingod字樣中同時(shí)出現(xiàn)，從而|A2

A5|=20!§6.1容斥原理第23頁|A1

A5|=0，|A4

A5|=19!，|A3

A4|=|A3

A5|=20!，|A3

A4

A5

|=17!，其余3個(gè)或多于3個(gè)集合交集都為空集。故滿足要求排列數(shù)為：26!-3

24!-2

22!+22!+4

20!+19!-17!=26!-3

24!-22!+4

20!+19!-17!§6.1容斥原理第24頁求多重集T={n1·a1,n2·a2,…,nk·ak}r-組合，若非全部ni皆等于1或皆≥r時(shí)怎樣求？例求多重集T={3·a,4·b,5·c}10-組合數(shù)。解：設(shè)T*={∞·a,∞·b,∞·c},S為T*全體10-組合集合，A1為T*含有多于3個(gè)a10-組合集合，A2為T*含有多于4個(gè)b10-組合集合，A3為T*含有多于5個(gè)c10-組合集合?！?.2含有重復(fù)組合第25頁=|S|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)-|A1A2A3|輕易求出，|S|=C(10+3-1,10)=66而A1與T*6-組合數(shù)相等(從A1任一組合中去掉4個(gè)a即得6-組合)。故|A1|=C(6+3-1,6)=28,…，最終求得

=66-(28+21+15)+(3+1+0)-0=6§6.2含有重復(fù)組合即為所求，由容斥原理，第26頁例求方程x1+x2+x3+x4=18滿足1≤x1≤5,-2≤x2≤4，0≤x3≤5，3≤x4≤9整數(shù)解個(gè)數(shù)。解作變量代換y1=x1-1,y2=x2+2,y3=x3,y4=x4-3,則問題變成求方程y1+y2+y3+y4=16滿足0≤y1≤4,0≤y2≤6，0≤y3≤5，0≤y4≤6整數(shù)解個(gè)數(shù)?！?.2含有重復(fù)組合第27頁設(shè)S為方程y1+y2+y3+y4=16全部非負(fù)整數(shù)解集合，A1、A2、A3、A4分別為滿足y1≥5,y2≥7,y3≥6,y4≥7非負(fù)整數(shù)解集合。則所求答案為：§6.2含有重復(fù)組合第28頁n個(gè)元素依次給以標(biāo)號(hào)1，2，…，n。n個(gè)元素全排列中，求每個(gè)元素都不在自己原來位置上排列數(shù)。設(shè)Ai為數(shù)i在第i位上全排列集合，

i=1,2,…,n，有：

|Ai|=(n-1)!，i=1,2,…,n，同理

|Ai

Aj|=(n-2)!，i、j=1,2,…,n，i

j…§6.3錯(cuò)位排列第29頁每個(gè)元素都不在原來位置排列數(shù)為=n!–C(n,1)(n-1)!§6.3錯(cuò)位排列+C(n,2)(n-2)!-…±C(n.n)1!{1,2,…,n}錯(cuò)排數(shù)記為Dn定理6.3.1Forn≥1，Dn第30頁e-1=1-1/1!+1/2!-1/3!+1/4!-…=Dn/n!+(-1)(n+1)/(n+1)!+(-1)(n+2)/(n+2)!+…e-1與Dn/n!差異小于1/(n+1)!，對(duì)n≥7，e-1

與Dn/n!在小數(shù)點(diǎn)后三位以內(nèi)都是相等。Dn是最靠近n!/e整數(shù)。例

10位球迷在球隊(duì)進(jìn)球時(shí)歡呼著將帽子拋向空中，一陣風(fēng)將帽子吹亂，每位球迷只好隨機(jī)地?fù)旎匾豁斆弊?。則每位球迷都沒有撿到自己帽子概率是D10/10!

e-1§6.3錯(cuò)位排列第31頁Dn滿足遞歸關(guān)系：Dn=(n-1)(Dn-2+Dn-1),(n=3,4,5,…)D1=0,D2=1證實(shí)：考慮n≥3，{1,2,…,n}錯(cuò)排分成(n-1)組，分別對(duì)應(yīng)2,3,…,n

放在第1個(gè)位置錯(cuò)排。當(dāng)i(i=2,3,…,n)放在第1個(gè)位置時(shí)錯(cuò)排數(shù)：

a)第i個(gè)位置放1，錯(cuò)排數(shù)為Dn-2；b)第i個(gè)位置不放1，錯(cuò)排數(shù)為Dn-1；§6.3錯(cuò)位排列第32頁遞歸關(guān)系可重寫為：

Dn-nDn-1=-[Dn-1-(n-1)Dn-2],n≥3=(-1)2[Dn-2-(n-2)Dn-3]

=…=(-1)n-2[D2-2D1]=(-1)nDn=nDn-1+(-1)n,n=2,3,4,…對(duì)照兩個(gè)關(guān)于階乘數(shù)遞歸公式：n!=(n-1)((n-2)!+(n-1)!)，n=3,4,5…n!=n(n-1)!n=2,3,4,…§6.3錯(cuò)位排列第33頁例

n位男士和n位女士參加舞會(huì)，有多少種方式搭配舞伴？假如在第一支舞跳完后，要求全部些人跳第二支舞時(shí)必須換舞伴，跳第二支舞時(shí)又有多少種方式搭配舞伴?答案：n!，Dn§6.3錯(cuò)位排列第34頁例在8個(gè)字母A,B,C,D,E,F,G,H全排列中,求使A,C,E,G四個(gè)字母不在原來位置上錯(cuò)排數(shù)目。解：8個(gè)字母全排列中，令A(yù)1,A2,A3,A4分別表A,C,E,G在原來位置上排列，則錯(cuò)排數(shù)為：=8!–C(4,1)7!+C(4,2)6!–C(4,3)5!+C(4,4)4!=24024§6.3錯(cuò)位排列第35頁例

求8個(gè)字母A,B,C,D,E,F,G,H全排列中只有4個(gè)不在原來位置排列數(shù)。解：8個(gè)字母中只有4個(gè)不在原來位置上，其余4個(gè)字母保持不動(dòng)，相當(dāng)于4個(gè)元素錯(cuò)排，其數(shù)目為§6.3錯(cuò)位排列第36頁故8個(gè)字母全排列中有4個(gè)不在原來位置上排列數(shù)應(yīng)為：C(8,4)·9=630§6.3錯(cuò)位排列第37頁§6.4帶有禁止位置排列

n個(gè)不一樣元素一個(gè)全排列可看做n個(gè)相同棋子在n×n棋盤上一個(gè)布局。布局滿足同一行(列)中有且僅有一個(gè)棋子。xxxxx如圖所表示布局對(duì)應(yīng)于排列41352。1．棋子多項(xiàng)式第38頁§6.4帶有禁止位置排列能夠把棋盤形狀推廣到任意形狀：布子要求稱為無對(duì)攻規(guī)則，棋子相當(dāng)于象棋中車。令r

k(C)表示k個(gè)棋子布到棋盤C上方案數(shù)。如：第39頁§6.4帶有禁止位置排列r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。為了形象化起見，（）中圖象便是棋盤形狀。第40頁定義設(shè)C為一棋盤，稱R(C)=∑rk(C)xk為C棋盤多項(xiàng)式。

要求r0(C)=1，包含C=

時(shí)。設(shè)Ci是棋盤C某一指定格子所在行與列都去掉后所得棋盤；Ce是僅去掉該格子后棋盤。在上面定義下，顯然有

rk(C)=rk－1(Ci)＋rk(Ce)，§6.4帶有禁止位置排列第41頁§6.4帶有禁止位置排列即對(duì)任一指定格子，要么布子，所得方案數(shù)為rk－1(Ci)；要么不布子，方案數(shù)為rk(Ce)。設(shè)C有n個(gè)格子，則r1(C)＝n．r1(C)＝r0(Ci)+r1(Ce)，∵r1(Ce)＝n－1∴r0(Ci)＝1．故要求r0(C)＝1是合理．第42頁§6.4帶有禁止位置排列

從上可得

R(C)=∑rk(C)xk

＝１＋∑[rk－1(Ci)+

rk(Ce)]xk=x∑rk(Ci)xk+∑rk(Ce)xk

＝xR(Ci)+R(C

e)(1)∞k=0∞∞∞k=0k=0k=0第43頁比如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=xR()+R()=x(1+x)+1+x=1+2x+x2§6.4帶有禁止位置排列第44頁§6.4帶有禁止位置排列假如C由相互分離C1，C2組成，即C1任一格子所在行和列中都沒有C2格子。則有：

rk(C)=∑ri(C1)rk－i(C2)i=0k故

R(C)=∑(∑ri(C1)rk－i(C2))xk

=(∑ri(C1)xi)(∑rj(C2)xj)j=0nnkni=0i=0k=0∴R(C)=R(C1)R(C2)(2)第45頁§6.4帶有禁止位置排列利用(1)和(2)，能夠把一個(gè)比較復(fù)雜棋盤逐步分解成相對(duì)比較簡(jiǎn)單棋盤，從而得到其棋盤多項(xiàng)式。例

R()=xR()+R()

=x(1+x)2+(1+2x)2=1+5x+6x2+x3*R()=xR()+R()=1+6x+10x2+4x3第46頁§6.4帶有禁止位置排列2．有禁區(qū)排列例設(shè)對(duì)于排列P=P1P2P3P4，要求P1≠3，P２≠1、4，P３≠2、4，P4≠2。1234P1P2P3P41243143223431214這么排列對(duì)應(yīng)于有禁區(qū)布子。如右圖有影線格子表示禁區(qū)。第47頁定理設(shè)ri為i個(gè)棋子布入禁區(qū)方案數(shù)，i=1,2,3,···,n。有禁區(qū)布子方案數(shù)（即禁區(qū)內(nèi)不布子方案數(shù)）為

r0n!－r1(n－1)!＋r2(n－2)!－···＋(－1)nrn＝∑(－1)krk

(n－k)!

k=0n證設(shè)Ai

為第i個(gè)棋子布入禁區(qū)，其它棋子任意布方案集，i=1,2,3,…,n?！?.4帶有禁止位置排列第48頁§6.4帶有禁止位置排列則全部棋子都不布入禁區(qū)方案數(shù)為｜A1∩A2∩···∩An｜＝n?。?－1)k∑｜∩Ai｜I∈￠(n,k)ni∈Ik=0而∑｜∩Ai｜正是k個(gè)棋子布入禁區(qū)，其他n-k個(gè)棋子任意布方案數(shù)。由假設(shè)可知等于rk(n－k)！(注意：布入禁區(qū)棋子也要恪守?zé)o對(duì)攻規(guī)則）.所以｜A1∩A2∩···∩An｜=n!+∑(－1)krk

(n－k)!I∈￠(n,k)i∈Ik=0

n第49頁上例方案數(shù)為4!－6(4－1)!＋11(4－2)!－7(4－3)!＋1(4－4)!＝4例

1，2，3，4四位工人，A，B，C，D四項(xiàng)任務(wù)。條件以下：

1不干B；2不干B、C；3不干C、D；4不干D。問有多少種可行方案？§6.4帶有禁止位置排列第50頁§6.4帶有禁止位置排列解由題意，可得以下棋盤：其中有影線格子表示禁區(qū)。ABCD1234

R()=1+6x+10x2+4x3

方案數(shù)=4!－6(4－1)!+10(4－2)!－4(4－3)!+0(4－4)!=4第51頁§6.4帶有禁止位置排列例

再論錯(cuò)排問題錯(cuò)排問題對(duì)應(yīng)是n×n棋盤主對(duì)角線上格子是禁區(qū)布子問題。C=···R(C)=(1+x)n=∑()xk令rk=()

nk=0

n

k

n

k故R(C)中xn:n!+∑(－1)k()(n－k)!=n!∑(－1)k－=Pnk=1

n

nk=0

k!1

k

n第52頁8個(gè)男生天天排成一隊(duì)去散步，除第一個(gè)人以外，每個(gè)人看到前面一個(gè)人后腦勺。第二天他們不愿意還是看著昨天那個(gè)人后腦勺，問有多少種方式重新排隊(duì)？設(shè)Qn為{1,2,…,n}排列中不出現(xiàn)12,23,…,(n-1)n

中任何一個(gè)排列數(shù)?！?.5另外禁排位置問題定理6.5.1Forn≥1

Qn=n!-C(n-1,1)(n-1)!+C(n-1,2)(n-2)!-C(n-1,3)(n-3)!+…+(-1)n-1C(n-1,n-1)第53頁§6.5另外禁排位置問題證設(shè)Aj(j=1,2,…,n-1)為{1,2,…,n}排列中出現(xiàn)了j(j+1)排列子集。則|Aj|=(n-1)!|Ai∩Aj|=(n-2)!…|Ai1∩Ai2∩…∩Aik

|=(n-k)!而Qn=|A1∩A2∩…∩An-1

|能夠證實(shí)Qn=Dn+Dn-1，(n≥2)

第54頁§6.6反演基本想法：{an}易算，{bn}難算，{an}可用｛bn｝表示，利用反演，將{bn}用{an}表示．１．二項(xiàng)式反演引理第55頁§6.6反演證

第56頁§6.6反演定理證第57頁推論證在定理中bk處用(－1)kbk代入，即可．例n!=∑()Dn－k，Dn=bn，令n－k=l，則n!=∑()DlDn=∑(－1)n-k()k!=n!∑(－1)n-k

=n∑nknknk1(n－k)!k=0k=0k=0nnn(－1)kk!§6.6反演第58頁§6.6反演２．Mǒbíus反演定義設(shè)n∈Z+

1，若n=1;μ(n)=0，若n=p1α1p2α2···pkαk存在αi>1(－1)k，若n=p1p2···pk

如μ(30)=μ(2·3·5)=(－1)3

μ(12)=0；第59頁定理設(shè)n∈Z+

則∑μ(d)=1，若n=1；0，若n>1；d|n證若n=1，∑μ(d)=μ(1)=1,成立．若

n>1，設(shè)n=p1α1p2α2···pkαk，n’=p1p2···pk

∑μ(d)=∑μ(d)=∑∑μ(∏pi)+μ(1)=1+∑()(－1)j=(1－1)k=0d|nd|nd|n’j=1ki∈II∈￠(k,j)kjj=1k§6.6反演第60頁§6.6反演推論

(n)=n∑μ(d)dd|n證

n∑=n∑=n·{1+∑(－1)j∑(∏pi)－1}=n∏(1－)=

(n)μ(d)dd|nμ(d)dd|n’1pij=1i=1kkI∈￠(k,j)i∈I第61頁§6.6反演定理(Mǒbíus反演定理)設(shè)f(n)和g(n)是定義在正整數(shù)集合上兩個(gè)函數(shù)．

f(n)=∑g(d)=∑g()(M1)g(n)=∑μ(d)f()=∑μ()f(d)(M2)ndndd|nd|nd|nd|n則(M1)(M2)nd第62頁§6.6反演證“”設(shè)(M1)成立?！痞?d)f()=∑μ(d)∑g(d1)=∑