版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,1,§3.5.1 集合的分劃與第二類Stirling數(shù) 定義3.5.1 集合S的子集族稱為n元集S的一個(gè)k-分劃，如果這個(gè)子集族滿足每個(gè)Si非空； 當(dāng)i≠j時(shí)， 其中每個(gè)Si稱為一個(gè)分劃塊，也把這個(gè)k-分劃記為：,集合的分劃與Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2,第二類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,3,第二類Sti
2、rling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,4,第二類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,5,第二類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,6,第二類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,7,第二類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,8,第二類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,9,第二類Stirlin
3、g數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,10,第二類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,11,作業(yè),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,12,第一類Stirling數(shù)也與集合的分劃相關(guān) 集合有A={1,2,3,4}7個(gè)2-分劃，但我們要求將每個(gè)分劃塊做成圓排列(或者輪換)，則共可構(gòu)成11個(gè)不同的圓排列組, 圖示見書63頁,第一類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,13
4、,2024/3/19,計(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),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,15,定理3.5.3 第一類Stirling數(shù)滿足如下遞推關(guān)系,第一類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,
5、16,證明：等式左邊 是將集合的k-圓排列分劃數(shù)，這些圓排列組可以分成兩類： 第1類：{an}單獨(dú)構(gòu)成一個(gè)圓排列，只需對(duì)集合A-{an}進(jìn)行(k-1)-圓排列分劃，再加上{an}這個(gè)圓排列，就構(gòu)成了A的k-圓排列分劃，因此，這類分劃有 個(gè)。,第一類Stirling數(shù),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,17,第2類： {an}不是A的k-圓排列分劃中的單獨(dú)一個(gè)圓排列，此時(shí)，先構(gòu)造A-{an}的k-圓
6、排列分劃，共有 種方法，然后對(duì)于A-{an}的每個(gè)k-圓排列分劃，將an插入該k-圓排列分劃的k個(gè)圓排列中的某一個(gè)圓排列中，共有n-1種不同的插入方法，因此集合A的此類k-圓排列分劃共有 個(gè)。 綜上以上分析，由加法原理，有,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,18,小結(jié)：S2(n,k) vs. S1(n,k),S2 (n,1)=1S2 (n,n)=1S2 (n,n-1)=C(n,2)S2
7、(n,k)=0(k>n)S2 (n+1,k)=S2 (n,k-1)+k?S2 (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(k>n) S1(n+1,k)= S1 (n,k-1)+n?S1 (n,k)S1 (n,k)的生成函數(shù)為P(x,n),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,19,正整數(shù)的分拆,2024/3/
8、19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,20,正整數(shù)的分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,21,正整數(shù)的分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,22,4的分拆,正整數(shù)的分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,23,正整數(shù)的分拆,集合的（無序）分劃A={a,b,c,d}A={a,b}∪{c} ∪2pnaklu ={a,c}∪ ∪qzxgafs ={a,d}∪ ∪{c} ={b,c}∪{a} ∪ylqhja2
9、={b,d}∪{a} ∪{c} ={c,d}∪{a} ∪S2(4,3)=C(4,2)=6A={1,1}∪{1} ∪{1}B(4,3)=1,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,24,有序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,25,有序分拆,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,26,有序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,27,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,28,有序分
10、拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,29,有序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,30,有序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,31,,,正偶數(shù)：,非負(fù)偶數(shù)：,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,32,有序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,33,有序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,34,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,35,無序分拆,2024/3/19,
11、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,36,無序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,37,無序分拆,B(n,1)=1B(n,n)=1B(n,n-1)=1B(n,2)= ?n/2?,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,38,無序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,39,無序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,40,無序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,41,無序分拆,2024/3/19,計(jì)算機(jī)
12、科學(xué)與技術(shù)學(xué)院,42,無序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,43,無序分拆,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,44,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,45,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,46,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,47,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,48,分拆的Ferr
13、ers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,49,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,50,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,51,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,52,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,53,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,54,分拆的Ferrers圖
14、,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,55,分拆的Ferrers圖,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,56,小結(jié)：S2(n,k) vs. B(n,k),S2 (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)+k?S2 (n,k)有序分劃k! S2 (n,k)S2 (n,k)有顯示表達(dá)式,B(n,1)=1B(n,n
15、)=1B(n,n-1)=1B(n,2)=?n/2?B(n+k,k)=B(n,1)+ B(n,2) + B(n,3)+…+B(n,k)有序分拆C(n-1,k-1)B(n,k)無顯示表達(dá)式,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,57,小結(jié),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,58,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,59,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,60,分配問題,2024/3/1
16、9,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,61,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,62,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,63,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,64,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,65,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,66,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,67,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,68,分
17、配問題,習(xí)題3.43．把n個(gè)不同的球放入m個(gè)不同的盒子里，允許有空盒，則放球的方法數(shù)為,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,69,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,70,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,71,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,72,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,73,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,74,分配問題,2
18、024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,75,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,76,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,77,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,78,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,79,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,80,分配問題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,81,作業(yè),pp. 83 3.8, 3.9, 3.1
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
評(píng)論
0/150
提交評(píng)論