《組合數(shù)學(xué)第三章ppt課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)第三章ppt課件.ppt（81頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,1,3.5.1 集合的分劃與第二類Stirling數(shù) 定義3.5.1 集合S的子集族稱為n元集S的一個(gè)k-分劃，如果這個(gè)子集族滿足每個(gè)Si非空； 當(dāng)ij時(shí)， 其中每個(gè)Si稱為一個(gè)分劃塊，也把這個(gè)k-分劃記為：,集合的分劃與Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,3,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,4,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,5,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

2、,6,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,7,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,8,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,9,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,10,第二類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,11,作業(yè),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,12,第一類Stirling數(shù)也與集合的分劃相關(guān) 集合有A=1,2,3,47個(gè)2-分劃，但我們要求將每個(gè)分劃塊做成圓排列(或者輪換)，則共可構(gòu)成11個(gè)不同的圓排列組, 圖示見書63頁,第一類St

3、irling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,13,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,14,定義3.5.3 一個(gè)n元集合的全部k-分劃所形成的不同的圓排列組的個(gè)數(shù)，即k-圓排列分劃數(shù)記為第一類Stirling數(shù)，表示為 或S1(n,k),性質(zhì)(1)性質(zhì)(2)性質(zhì)(3)性質(zhì)(4),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,15,定理3.5.3 第一類Stirling數(shù)滿足如下遞推關(guān)系,第一類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,16,證明：等式左邊 是將集合的k-圓排列分劃數(shù)，這些圓排列組可以分成兩類： 第1類：an單獨(dú)構(gòu)成一個(gè)圓排列，只需對集合A-an進(jìn)行(

4、k-1)-圓排列分劃，再加上an這個(gè)圓排列，就構(gòu)成了A的k-圓排列分劃，因此，這類分劃有 個(gè)。,第一類Stirling數(shù),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,17,第2類： an不是A的k-圓排列分劃中的單獨(dú)一個(gè)圓排列，此時(shí)，先構(gòu)造A-an的k-圓排列分劃，共有 種方法，然后對于A-an的每個(gè)k-圓排列分劃，將an插入該k-圓排列分劃的k個(gè)圓排列中的某一個(gè)圓排列中，共有n-1種不同的插入方法，因此集合A的此類k-圓排列分劃共有 個(gè)。 綜上以上分析，由加法原理，有,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,18,小結(jié)：S2(n,k) vs. S1(n,k),S2 (n,1)=1S2 (n,n)

5、=1S2 (n,n-1)=C(n,2)S2 (n,k)=0(kn)S2 (n+1,k)=S2 (n,k-1)+kS2 (n,k)S2 (n,k)的生成函數(shù)為,S1(n,1)=(n-1)!S1(n,n)=1S1(n,n-1)=C(n,2)S1 (n,k)=0(kn) S1(n+1,k)= S1 (n,k-1)+nS1 (n,k)S1 (n,k)的生成函數(shù)為P(x,n),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,19,正整數(shù)的分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,20,正整數(shù)的分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,21,正整數(shù)的分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,22,4的

6、分拆,正整數(shù)的分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,23,正整數(shù)的分拆,集合的（無序）分劃A=a,b,c,dA=a,bc d =a,cb d =a,db c =b,ca d =b,da c =c,da bS2(4,3)=C(4,2)=6A=1,11 1B(4,3)=1,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,24,有序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,25,有序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,26,有序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,27,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,28,有序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,29,有序分

7、拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,30,有序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,31,正偶數(shù)：,非負(fù)偶數(shù)：,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,32,有序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,33,有序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,34,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,35,無序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,36,無序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,37,無序分拆,B(n,1)=1B(n,n)=1B(n,n-1)=1B(n,2)= n/2,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,38,無序分拆,2022/4/

8、8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,39,無序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,40,無序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,41,無序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,42,無序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,43,無序分拆,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,44,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,45,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,46,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,47,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,48,分拆的F

9、errers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,49,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,50,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,51,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,52,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,53,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,54,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,55,分拆的Ferrers圖,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,56,小結(jié)：S2(n,k) vs. B(n,k),S2

10、 (n,1)=1S2 (n,n)=1S2 (n,n-1)=C(n,2)S2 (n,2)=2n-1-1S2 (n+1,k)=S2 (n,k-1)+kS2 (n,k)有序分劃k! S2 (n,k)S2 (n,k)有顯示表達(dá)式,B(n,1)=1B(n,n)=1B(n,n-1)=1B(n,2)=n/2B(n+k,k)=B(n,1)+ B(n,2) + B(n,3)+B(n,k)有序分拆C(n-1,k-1)B(n,k)無顯示表達(dá)式,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,57,小結(jié),2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,58,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,59,分配問題,2022/

11、4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,60,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,61,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,62,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,63,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,64,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,65,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,66,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,67,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,68,分配問題,習(xí)題3.43把n個(gè)不同的球放入m個(gè)不同的盒子里，允許有空盒，則放球的方法數(shù)為,2022/4/8,計(jì)算機(jī)科學(xué)

12、與技術(shù)學(xué)院,69,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,70,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,71,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,72,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,73,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,74,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,75,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,76,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,77,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,78,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,79,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,80,分配問題,2022/4/8,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,81,作業(yè),pp. 83 3.8, 3.9, 3.17, 3.21(1), 3.24, 3.25,