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