廣義容斥原理及其應(yīng)用

1、廣義容斥原理及其應(yīng)用主講人：主講人： 0901340809013408 黃穎黃穎 第第1111組小組成員：組小組成員： 0901330209013302 蔡萌蔡萌09013304 09013304 景昕蕊景昕蕊 09013406 09013406 周宇池周宇池例：院系圖書借記表統(tǒng)計(jì)了一個(gè)月內(nèi)組合數(shù)學(xué)、西游記、院系圖書借記表統(tǒng)計(jì)了一個(gè)月內(nèi)組合數(shù)學(xué)、西游記、算法導(dǎo)論三本書的借記統(tǒng)計(jì)情況，借這三本書的人數(shù)分別算法導(dǎo)論三本書的借記統(tǒng)計(jì)情況，借這三本書的人數(shù)分別是是6262、4545、3333，同時(shí)借了組合數(shù)學(xué)、西游記的有，同時(shí)借了組合數(shù)學(xué)、西游記的有2323人，人，同時(shí)借了組合數(shù)學(xué)、算法導(dǎo)論的有同時(shí)借

2、了組合數(shù)學(xué)、算法導(dǎo)論的有1818人，同時(shí)借了人，同時(shí)借了西游記、算法導(dǎo)論的有西游記、算法導(dǎo)論的有1010人，同時(shí)借了三本書的有人，同時(shí)借了三本書的有3 3人。人。問：本月借了這三本書的共有多少人？問：本月借了這三本書的共有多少人？文氏圖簡單解決問題A:A:借組合數(shù)學(xué)借組合數(shù)學(xué)B:B:借西游記借西游記C:C:借算法導(dǎo)論借算法導(dǎo)論同時(shí)借這三本書的人數(shù)設(shè)為同時(shí)借這三本書的人數(shù)設(shè)為M MM=|AM=|AB BC|C|A 24B15C 8203157若將問題修改成若將問題修改成“只借組合數(shù)學(xué)的人數(shù)只借組合數(shù)學(xué)的人數(shù)Y Y？”，“只借一本只借一本書的人數(shù)書的人數(shù)Z Z？”Y=Y=同理：記同理：記 Y1=Y

3、1= Y2= Y2= Z=Y+Y1+Y2 Z=Y+Y1+Y2ABCAABACABCABCBBABCABCABCCCACBABC容斥原理與廣義容斥原理 容斥原理解容斥原理解 決的問題：決的問題：廣義容斥原理解決的問題：廣義容斥原理解決的問題：|n21AAA|n_2_1_AAA|n_1_21AAAAAii廣義容斥原理設(shè)有與性質(zhì)設(shè)有與性質(zhì),2,n相關(guān)的元素相關(guān)的元素N個(gè)，個(gè)，Ai為有第為有第 i 種性質(zhì)的元素的種性質(zhì)的元素的集合集合. .i=1,2,n定義定義a(0)=n；當(dāng)；當(dāng)m1時(shí)時(shí)b( (m) )是正好具有是正好具有m個(gè)性質(zhì)的元素的個(gè)數(shù)。個(gè)性質(zhì)的元素的個(gè)數(shù)。12( )miiia mAAA|b(

4、0)n_2_1_AAA|b(m)n121i_AAAAAmmiiii例如，對(duì)于例如，對(duì)于n=3,=3,m=2=2利用這些記號(hào)利用這些記號(hào) b(1)=a(1)-2a(2)+3a(3)b(2)=a(2)-3a(3)121323(2)aAAAAAA212313123(2) bAAAAAAAAA廣義容斥原理廣義容斥原理定理（廣義容斥原理）：定理（廣義容斥原理）：推論：當(dāng)推論：當(dāng)m=0時(shí)時(shí)1( )( )(1)( 1)( ) ( 1)( )n mnk mk mmnb ma ma ma nmmka km (0)(0)(1)(2)( 1)( )nbaaaa n 廣義容斥原理一個(gè)應(yīng)用在組合數(shù)學(xué)，Stirling數(shù)

5、可指兩類數(shù)，都是由18世紀(jì)數(shù)學(xué)家James Stirling提出的。第一類Stirling數(shù)是有正負(fù)的，其絕對(duì)值是n個(gè)元素的項(xiàng)目分作k個(gè)環(huán)排列的方法數(shù)目S(n,k)。換個(gè)較生活化的說法，就是有n個(gè)人分成k組，每組內(nèi)再按特定順序圍圈的分組方法的數(shù)目。第二類Stirling數(shù)是n個(gè)元素的集定義k個(gè)等價(jià)類的方法數(shù)目S(n,k)。換個(gè)較生活化的說法，就是有n個(gè)人分成k組的分組方法的數(shù)目。第二類第二類StirlingStirling數(shù)的展開式數(shù)的展開式 s(4,2)=11第二類Stirling數(shù)的展開式n n個(gè)有區(qū)別的球放到個(gè)有區(qū)別的球放到m m個(gè)相同的盒子中（個(gè)相同的盒子中（nmnm），要求無一空盒，

6、其），要求無一空盒，其不同的方案數(shù)用不同的方案數(shù)用S(n,m)S(n,m)表示，稱為第二類表示，稱為第二類StirlingStirling數(shù)。即數(shù)。即S(n,m)S(n,m)也就是將也就是將n n個(gè)數(shù)拆分成非空的個(gè)數(shù)拆分成非空的m m個(gè)部分的方案數(shù)。個(gè)部分的方案數(shù)。mknkkmkmCm0)(,() 1(!1m)S(n,Ai表示第i個(gè)盒為空,其它盒任意的方案數(shù)（i=1,2,m）?？紤]考慮n n個(gè)有標(biāo)志的球，放進(jìn)個(gè)有標(biāo)志的球，放進(jìn)m m個(gè)有區(qū)別的盒子，得到無一空盒的方案數(shù)為個(gè)有區(qū)別的盒子，得到無一空盒的方案數(shù)為 mA.AA21）mS(n,m! 第二類Stirling數(shù)的展開式 miijjiAAa1)2(nm)2(2m miiiiiiiikkkAAAka1112121.)(nkmk)(mmAAAa.)1 (21nm)1(1mnmNa)0(第二類Stirling數(shù)的展開式n個(gè)有標(biāo)志的球，放進(jìn)m個(gè)無區(qū)別的盒子，無一空盒的方案數(shù)為：)(