組合數(shù)學(xué)--第三章第三節(jié)廣義的容斥原理ppt課件

1、第第3章章 容斥原理與鴿巢原理容斥原理與鴿巢原理 3.1 De Morgan 3.1 De Morgan定理定理 1 1 3.2 3.2 容斥原理容斥原理 1 1 3.3 3.3 容斥原理舉例容斥原理舉例 1 1 3.4 3.4 棋盤多項(xiàng)式與有限制的排列棋盤多項(xiàng)式與有限制的排列 2 2 3.5 3.5 有禁區(qū)的排列有禁區(qū)的排列 2 2 3.6 3.6 廣義的容斥原理廣義的容斥原理 2 2 3.7 3.7 廣義容斥原理的應(yīng)用廣義容斥原理的應(yīng)用 3 3 2.8 2.8 第二類第二類StirlingStirling數(shù)的展開式數(shù)的展開式 1 1 2.9 2.9 歐拉函數(shù)歐拉函數(shù)(n) 1(n) 1 2

2、.10 n 2.10 n對(duì)夫妻問題對(duì)夫妻問題 3 3 * *2.11 Mobius2.11 Mobius反演定理反演定理 2.12 2.12 鴿巢原理鴿巢原理 4 4 2.13 2.13 鴿巢原理舉例鴿巢原理舉例 4 4 2.14 2.14 鴿巢原理的推廣鴿巢原理的推廣 4 4 * *2.15 Ramsey2.15 Ramsey數(shù)數(shù) 3.6 廣義的容斥原理廣義的容斥原理容斥原理解決的問題容斥原理解決的問題:nAAA.21 nA.AA21廣義的容斥原理解決的問題廣義的容斥原理解決的問題niiA.A.AAA1213.6 廣義的容斥原理廣義的容斥原理 求只參加了數(shù)學(xué)課的人數(shù)？求只參加了數(shù)學(xué)課的人數(shù)？

3、 只參加了物理課的人數(shù)？只參加了物理課的人數(shù)？ 只參加了化學(xué)課的人數(shù)？只參加了化學(xué)課的人數(shù)？ 例例3.6.1：一個(gè)學(xué)校只有數(shù)學(xué)，物理，化：一個(gè)學(xué)校只有數(shù)學(xué)，物理，化學(xué)學(xué)3門課門課 。學(xué)這。學(xué)這3門課的學(xué)生人數(shù)分別是門課的學(xué)生人數(shù)分別是170,130,120；同時(shí)學(xué)數(shù)學(xué)、物理兩門課的學(xué)；同時(shí)學(xué)數(shù)學(xué)、物理兩門課的學(xué)生有生有45人；同時(shí)學(xué)數(shù)學(xué)、化學(xué)的有人；同時(shí)學(xué)數(shù)學(xué)、化學(xué)的有20人；同人；同時(shí)學(xué)物理、化學(xué)的有時(shí)學(xué)物理、化學(xué)的有22人；同時(shí)修三門課的人；同時(shí)修三門課的學(xué)生有學(xué)生有3人，問這個(gè)學(xué)校共有多少學(xué)生人，問這個(gè)學(xué)校共有多少學(xué)生? 只參加了數(shù)學(xué)、物理課的人數(shù)？只參加了數(shù)學(xué)、物理課的人數(shù)？ 只參加了

4、數(shù)學(xué)、化學(xué)課的人數(shù)？只參加了數(shù)學(xué)、化學(xué)課的人數(shù)？CPM 單修一門數(shù)學(xué)，即修數(shù)學(xué)而不修物理和單修一門數(shù)學(xué)，即修數(shù)學(xué)而不修物理和化學(xué)的學(xué)生數(shù)；可如下表示：化學(xué)的學(xué)生數(shù)；可如下表示： 解：設(shè)解：設(shè)M為修數(shù)學(xué)課的學(xué)生集合；為修數(shù)學(xué)課的學(xué)生集合；P為修為修物理課的學(xué)生集合；物理課的學(xué)生集合；C為修化學(xué)課的學(xué)生集合，為修化學(xué)課的學(xué)生集合， 求只參加了數(shù)學(xué)課的人數(shù)？求只參加了數(shù)學(xué)課的人數(shù)？3.6 廣義的容斥原理廣義的容斥原理CPM)()(CMPMMCPM關(guān)于關(guān)于M M互為補(bǔ)集互為補(bǔ)集1083)2045(170MPC)()()(CPMCMPMM)()(CMPM因此：只參加數(shù)學(xué)課因此：只參加數(shù)學(xué)課學(xué)習(xí)的人數(shù)有學(xué)

5、習(xí)的人數(shù)有3.6 廣義的容斥原理廣義的容斥原理只學(xué)數(shù)學(xué)、物理兩門課只學(xué)數(shù)學(xué)、物理兩門課CPM)()(CPMPM42345MPC3.6 廣義的容斥原理廣義的容斥原理*3.6.1 3.6.1 一般公式一般公式假定全集是假定全集是N,N,其中有其中有A1,A2,AnA1,A2,An個(gè)子集，個(gè)子集，定義：當(dāng)定義：當(dāng)m0m0時(shí)時(shí)miiiAAAm.)(21對(duì)于特殊情況對(duì)于特殊情況m=0m=0時(shí)定義時(shí)定義: :N)0(3.6 廣義的容斥原理廣義的容斥原理nAAA. 21nnniijjhhjiniijjiniiAAAAAAAAAN.)1( . 21111 )(mnmmmiiiiiiAAAAAAm.)(2121

6、nAAA.) 0(213.6 廣義的容斥原理廣義的容斥原理 定義定義 是正好存在于是正好存在于m m個(gè)集合的元素個(gè)集合的元素的個(gè)數(shù)的個(gè)數(shù) 例例3.6.2 3.6.2 設(shè)設(shè)N=1,2,3,14,4N=1,2,3,14,4個(gè)集合個(gè)集合A1,A2,A3,A4A1,A2,A3,A4。 A1=2,5,8,12,13, A1=2,5,8,12,13,； A2=1,3,5,6,7,8,10,12,14 A2=1,3,5,6,7,8,10,12,14； A3=1,4,5,7,12,13 A3=1,4,5,7,12,13； A4=1,4,5,7,12,14 A4=1,4,5,7,12,14。3.6 廣義的容斥原

7、理廣義的容斥原理N123456789 10 11 12 13 14A1A2A3A4m=0m=0時(shí)時(shí), ,14) 0( Nm=1m=1時(shí)時(shí), ,266695) 1 (4321AAAAm=2m=2時(shí)時(shí), ,434232413121 )2(AAAAAAAAAAAA225542333.6 廣義的容斥原理廣義的容斥原理m=4m=4時(shí)時(shí), ,2)4(4321AAAA4321) 0 (AAAA4321432143214321) 1 (AAAAAAAAAAAAAAAA 432143214321432143214321 ) 2 (AAAAAAAAAAAAAAAAAAAAAAAA440031211, 93.6 廣

8、義的容斥原理廣義的容斥原理N123456789 10 11 12 13 14A1A2A3A4定理定理3.3.4 3.3.4 廣義容斥原理的證明廣義容斥原理的證明)(),() 1( .)2(), 2() 1(), 1()()(nmnCmmmCmmmCmmmn證明：證明：miiiAAAm.)(21 aN,aN,設(shè)它屬于設(shè)它屬于t t個(gè)集合個(gè)集合分分tmtm三種情況來討論三種情況來討論(1)(1)若若tm,tm,tm, 因?yàn)樽蠖耸钦么嬖谟谝驗(yàn)樽蠖耸钦么嬖谟趍 m個(gè)集合的元素，因個(gè)集合的元素，因此左端沒有計(jì)算此左端沒有計(jì)算a a，在右端的情況分析如下：在右端的情況分析如下：3.6 廣義的容斥原理廣

9、義的容斥原理)(),() 1( .) 2(), 2() 1(), 1()()(nmnCmmmCmmmCmmmnmiiiAAAm.)(21nmmmiiiiiiAAAAAAm.)(2121.次中計(jì)算了在),()(ttCta設(shè)設(shè)a a包含在包含在t t個(gè)集合中個(gè)集合中,A1,A2,.,At,A1,A2,.,At，tm,tm,?)(中計(jì)算了多少次在ma),( mtC3.6 廣義的容斥原理廣義的容斥原理) 1,(mtC？m中計(jì)算多少次在) 1(a)(),() 1( .) 2(), 2() 1(), 1()()(nmnCmmmCmmmCmmmnmiiiAAAm.)(21),(),() 1( .) 2,()

10、, 2() 1,(), 1(),(ttCmtCmtCmmCmtCmmCmtClmt3.6 廣義的容斥原理廣義的容斥原理設(shè)設(shè)a a包含在包含在t t個(gè)集合中個(gè)集合中,A1,A2,.,At,A1,A2,.,At，tm,tm, 因?yàn)樽蠖耸钦么嬖谟谝驗(yàn)樽蠖耸钦么嬖谟趍 m個(gè)集合的元素，因個(gè)集合的元素，因此左端沒有計(jì)算此左端沒有計(jì)算a a， 右端關(guān)于右端關(guān)于a a的計(jì)算的計(jì)算: :), (), () 1( .), 2() 2, (), 1() 1, (), (mtCttCmmCmtCmmCmtCmtClmt),(),() 1( .), 2() 2,(), 1() 1,(),(mtCttCmmCmtC

11、mmCmtCmtClmt3.6 廣義的容斥原理廣義的容斥原理利用公式：利用公式：),(),(),(),(rkrnCrnCrkCknC),(),() 1( .)2 ,(),() 1 ,(),(),(mtmtCmtCmtCmtCmtCmtCmtClmt),() 1( .)2 ,() 1 ,(1),(mtmtCmtCmtCmtCmt),() 1(.)2 ,() 1 ,(1),(mtmtCmtCmtCmtCmt 中括號(hào)各項(xiàng)正好是中括號(hào)各項(xiàng)正好是(1-x)t-m(1-x)t-m的系數(shù)的系數(shù), , mtmtmtxmtmtCxmtCxmtCx),() 1(.)2 ,() 1 ,(1)1 (23.6 廣義的容

12、斥原理廣義的容斥原理如果令如果令x=1,x=1,得到：得到：0),() 1(.)2 ,() 1 ,(1mtmtCmtCmtCmt綜合以上三種情況：綜合以上三種情況：)(),() 1( .)2(), 2() 1(), 1()()(nmnCmmmCmmmCmmmn推論推論3.13.1)() 1(.)2() 1 ()0()0(nn3.6 廣義的容斥原理廣義的容斥原理 aN,aN,設(shè)它屬于設(shè)它屬于t t個(gè)集合個(gè)集合分分tmtm三種情況來討論三種情況來討論3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用線性方程整數(shù)解的問題線性方程整數(shù)解的問題rxxxn.21 的零或正整數(shù)解的數(shù)目，其中的零或正整數(shù)解

13、的數(shù)目，其中x1,x2,xnx1,x2,xn是變量，是變量，n1,r0,nn1,r0,n和和r r都是正整數(shù)。都是正整數(shù)。 這個(gè)方程的任一非負(fù)整數(shù)解都可以看做是這個(gè)方程的任一非負(fù)整數(shù)解都可以看做是r r個(gè)無個(gè)無區(qū)別的球放進(jìn)區(qū)別的球放進(jìn)n n個(gè)有標(biāo)志個(gè)有標(biāo)志x1,x2,xnx1,x2,xn的盒子，允許的盒子，允許空盒，空盒，), 1(rrnC例例3.6.4 3.6.4 求方程求方程x1+x2+x3=15x1+x2+x3=15的整數(shù)解的數(shù)目，的整數(shù)解的數(shù)目，要求要求0 x15,0 x26,0 x370 x15,0 x26,0 x37。如果沒有附加條件，即求：如果沒有附加條件，即求： x1+x2+x

14、3=15 x1+x2+x3=15的零或正的零或正整數(shù)解，即要求：整數(shù)解，即要求： x10 x10，x20 x20，x30 x30。 C(3+15-1,15)=C(17,15)=C(17,2)C(3+15-1,15)=C(17,15)=C(17,2)變?yōu)橛懻搯栴}變?yōu)橛懻搯栴}x1+x2+x3=15x1+x2+x3=15的整數(shù)解，求：的整數(shù)解，求：x16x16，x27x27，x38x38。3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用例例3.6.4 3.6.4 求方程求方程x1+x2+x3=15x1+x2+x3=15的整數(shù)解的數(shù)目，的整數(shù)解的數(shù)目，要求要求0 x15,0 x26,0 x370

15、x15,0 x26,0 x37。解解: :令令N N為全體非負(fù)整數(shù)解為全體非負(fù)整數(shù)解(x1,x2,x3),(x1,x2,x3),A1A1為其中為其中x16x16的解；的解；A2A2為其中為其中x27x27的解；的解；A3A3為其中為其中x38x38的解。的解。3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用 A1 A1的個(gè)數(shù)，相當(dāng)于對(duì)的個(gè)數(shù)，相當(dāng)于對(duì)y1+6y1+6）+x2+x3=15+x2+x3=15求非負(fù)求非負(fù)整數(shù)解的個(gè)數(shù)。整數(shù)解的個(gè)數(shù)。C(3+9-1,9)=C(11,2)C(3+9-1,9)=C(11,2)y1=x1-60y1=x1-60的解；的解；y2=x2-70y2=x2-70的

16、解；的解；y3=x3-80y3=x3-80的解。的解。A2A2的個(gè)數(shù)，相當(dāng)于對(duì)的個(gè)數(shù)，相當(dāng)于對(duì)x1+(y2+7)+x3=15x1+(y2+7)+x3=15求非負(fù)求非負(fù)整整數(shù)解的個(gè)數(shù)。數(shù)解的個(gè)數(shù)。C(3+8-1,8)=C(10,2)C(3+8-1,8)=C(10,2)A3A3的個(gè)數(shù)，相當(dāng)于對(duì)的個(gè)數(shù)，相當(dāng)于對(duì)x1+x2+(y3+8)=15x1+x2+(y3+8)=15求非負(fù)求非負(fù)整整數(shù)解的個(gè)數(shù)。數(shù)解的個(gè)數(shù)。C(3+7-1,7)=C(9,2)C(3+7-1,7)=C(9,2)3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用) 2 , 9 (),2 ,10(),2 ,11(),2 ,17(321C

17、ACACACN性質(zhì)性質(zhì)A1A2A1A2的個(gè)數(shù)，相當(dāng)于對(duì)的個(gè)數(shù)，相當(dāng)于對(duì)（y1+6y1+6）+(y2+7)+x3=15+(y2+7)+x3=15求非負(fù)整數(shù)解的個(gè)數(shù)。求非負(fù)整數(shù)解的個(gè)數(shù)。即求即求y1+y2+x3=2y1+y2+x3=2的非負(fù)整數(shù)解，其解的個(gè)數(shù)為的非負(fù)整數(shù)解，其解的個(gè)數(shù)為C(3+2-1,2)=C(4,2)C(3+2-1,2)=C(4,2)性質(zhì)性質(zhì)A1A3A1A3的解的個(gè)數(shù)，相當(dāng)于對(duì)的解的個(gè)數(shù)，相當(dāng)于對(duì)(y1+6)+x2+(y3+8)=15(y1+6)+x2+(y3+8)=15求非負(fù)整數(shù)解的個(gè)數(shù)。求非負(fù)整數(shù)解的個(gè)數(shù)。即求即求y1+x2+y3=1y1+x2+y3=1的非負(fù)整數(shù)解，其解的個(gè)

18、數(shù)為的非負(fù)整數(shù)解，其解的個(gè)數(shù)為C(3+1-1,1)=C(3,1)C(3+1-1,1)=C(3,1)3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用性質(zhì)性質(zhì)A2A3A2A3的個(gè)數(shù)，相當(dāng)于對(duì)的個(gè)數(shù)，相當(dāng)于對(duì)x1+(y2+7)+(y3+8)=15x1+(y2+7)+(y3+8)=15求非負(fù)整數(shù)解的個(gè)數(shù)。求非負(fù)整數(shù)解的個(gè)數(shù)。即求即求x1+y2+y3=0 x1+y2+y3=0的非負(fù)整數(shù)解，其解的個(gè)數(shù)為的非負(fù)整數(shù)解，其解的個(gè)數(shù)為C(3+0-1,0)=C(2,0)C(3+0-1,0)=C(2,0) 2 , 9 (),2 ,10(),2 ,11(),2 ,17(321CACACACN) 0 , 2(),1

19、 , 3 (),2 , 4(323121CAACAACAA3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用 性質(zhì)性質(zhì)A1A2A3A1A2A3的個(gè)數(shù)，相當(dāng)于對(duì)的個(gè)數(shù)，相當(dāng)于對(duì)(y1+6)+(y2+7)+(y3+8)=15(y1+6)+(y2+7)+(y3+8)=15求非負(fù)整數(shù)解的個(gè)數(shù)。求非負(fù)整數(shù)解的個(gè)數(shù)。即求即求y1+y2+y3=-6y1+y2+y3=-6的非負(fù)整數(shù)解，其解的個(gè)數(shù)的非負(fù)整數(shù)解，其解的個(gè)數(shù)0 00321AAA) 3 () 2 () 1 () 0 () 0 (100)0 , 2 () 1 , 3 () 2 , 4 ()2 , 9 () 2 ,10() 2 ,11() 2 ,17(

20、CCCCCCC3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用例例3.6.5 3.6.5 求方程求方程x1+x2+x3=15x1+x2+x3=15的整數(shù)解的數(shù)目，的整數(shù)解的數(shù)目，要求要求3x15,2x26,1x373x15,2x26,1x37。3.7 廣義容斥原理的若干應(yīng)用廣義容斥原理的若干應(yīng)用作變換作變換0 x1-32,0 x2-24,0 x3-160 x1-32,0 x2-24,0 x3-16。FHABCDEGO(0,0)P(10,5) 例例3.6.63.6.6：如下圖，：如下圖， 1 1、求從、求從O(0,0)O(0,0)點(diǎn)到點(diǎn)到P(10,5)P(10,5)點(diǎn)的路徑中不通過點(diǎn)的路徑中

21、不通過AB,CD,EF,GHAB,CD,EF,GH中任何一條路徑的路徑數(shù)。中任何一條路徑的路徑數(shù)。 坐標(biāo)分別為坐標(biāo)分別為:A(2,2),B(3,2),C(4,2),:A(2,2),B(3,2),C(4,2),D(5,2),E(6,2),F(6,3),G(7,2),H(7,3)D(5,2),E(6,2),F(6,3),G(7,2),H(7,3)。 2 2、只通過其中兩個(gè)的路徑數(shù)。、只通過其中兩個(gè)的路徑數(shù)。路徑數(shù)問題路徑數(shù)問題:FHABCDEGO(0,0)P(10,5)解：令解：令A(yù)1A1為從為從O O點(diǎn)到點(diǎn)到P P點(diǎn)過點(diǎn)過ABAB邊的路徑；邊的路徑； 令令A(yù)2A2為從為從O O點(diǎn)到點(diǎn)到P P點(diǎn)過

22、點(diǎn)過CDCD邊的路徑；邊的路徑； 令令A(yù)3A3為從為從O O點(diǎn)到點(diǎn)到P P點(diǎn)過點(diǎn)過EFEF邊的路徑；邊的路徑； 令令A(yù)4A4為從為從O O點(diǎn)到點(diǎn)到P P點(diǎn)過點(diǎn)過GHGH邊的路徑；邊的路徑；) 3 ,10() 2 , 4(1CCA ) 3 , 8 () 2 , 6(2CCA ) 2 , 6() 2 , 8 (3CCA ) 2 , 5 () 2 , 9 (4CCA 路徑數(shù)問題路徑數(shù)問題:) 2 , 6)(2 , 4 (321CAAA) 2 , 5)(2 , 4 (421CAAA0431AAA0432AAA04321AAAA) 3 , 8 () 2 , 4 (21CCAA) 2 , 6 () 2 ,

23、 4 (31CCAA) 2 , 5 () 2 , 4 (41CCAA) 2 , 6 () 2 , 6 (32CCAA) 2 , 5 () 2 , 6 (42CCAA043AA 路徑數(shù)問題路徑數(shù)問題:FHABCDEGO(0,0)P(10,5)如果求正好過上述四條線段中兩條的路徑數(shù)如果求正好過上述四條線段中兩條的路徑數(shù))4()2 , 4()3()2 , 3()2()2(CC)2 , 5 () 2 , 6 () 2 , 6 () 2 , 6 () 2 , 5 () 2 , 4() 2 , 6 () 2 , 4() 3 , 8 () 2 , 4(CCCCCCCCCC)2 , 5()2 , 4()2 ,

24、 6()2 , 4(3CCCC) 4() 3 () 2() 1 () 0() 0() 2 , 5 () 2 , 9 () 2 , 6() 2 , 8 () 3 , 8 () 2 , 6() 3 ,10() 2 , 4() 5 ,15(CCCCCCCCC 0) 2 , 5 () 2 , 6 () 2 , 6 () 2 , 6 () 2 , 5 () 2 , 4 () 2 , 6 () 2 , 4 () 3 , 8 () 2 , 4 (CCCCCCCCCC)2 , 5 () 2 , 4 () 2 , 6 () 2 , 4 (CCCC不通過上述四條線段中任何一條的路徑數(shù)不通過上述四條線段中任何一條的

25、路徑數(shù)路徑數(shù)問題路徑數(shù)問題:*1 1、求、求n n對(duì)夫妻排成一行，夫妻相鄰的排列數(shù)。對(duì)夫妻排成一行，夫妻相鄰的排列數(shù)。解：解：nnn2!)(3.10,n對(duì)夫妻問題。對(duì)夫妻問題。2 2、求、求n n對(duì)夫妻排成一行，夫妻不相鄰的排列數(shù)。對(duì)夫妻排成一行，夫妻不相鄰的排列數(shù)。解：設(shè)解：設(shè)AiAi是第是第i i對(duì)夫妻排在一起的排列集。對(duì)夫妻排在一起的排列集。正好有正好有m m對(duì)夫妻排在一起的方案數(shù)對(duì)夫妻排在一起的方案數(shù)解：設(shè)解：設(shè)AiAi是第是第i i對(duì)夫妻排在一起的排列集。對(duì)夫妻排在一起的排列集。2)!12(nAi22)!22(nAAjihihiihnAAA2)!2(.21nn2)!12() 1 ()2 ,(2)!22()2(2nCn),(2)!2()(hnChnhhnnn2!)(3.10,n對(duì)夫妻問題。對(duì)夫妻問題。nnnnnCnnCnnCn2!),() 1(.2)!22)(2 ,(2)!12)(1 ,()!2() 0(2)() 1(.) 2() 1 () 0 () 0 (nn3.10,n對(duì)夫妻問題。對(duì)夫妻問題。)(),() 1( .) 2(), 2() 1(), 1()()(nmnCmmmCmmmCmmmn正好有正好有m m對(duì)夫妻排在一起的方案數(shù)對(duì)夫妻排在一起的方案數(shù)3,n3,n對(duì)夫妻圍一圓桌而坐，夫妻相鄰的排列數(shù)。對(duì)夫妻