組合數(shù)學第三章(3)

1、2022-3-25計算機科學與技術(shù)學院13.5.1 集合的分劃與第二類集合的分劃與第二類Stirling數(shù)數(shù) 定義定義3.5.1 集合S的子集族稱為n元集S的一個k-分劃，如果這個子集族滿足每個Si非空； 當ij時， 其中每個Si稱為一個分劃塊，也把這個k-分劃記為： 21k，S，SSijSS 集合的分劃與集合的分劃與Stirling數(shù)數(shù)kSSSS21kSSSS212022-3-25計算機科學與技術(shù)學院2第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院3第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院4第二類第二類Stirling數(shù)數(shù)2022-3-2

2、5計算機科學與技術(shù)學院5第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院6第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院7第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院8第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院9第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院10第二類第二類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院11作業(yè)作業(yè)2022-3-25計算機科學與技術(shù)學院12 第一類Stirling數(shù)也與集合的分劃相關(guān) 集合有A=1,2,3,47個2-分劃，但我們

3、要求將每個分劃塊做成圓排列(或者輪換)，則共可構(gòu)成11個不同的圓排列組, 圖示見書63頁第一類第一類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院132022-3-25計算機科學與技術(shù)學院14定義定義3.5.3 一個一個n元集合的全部元集合的全部k-分劃所分劃所形成的不同的圓排列組的個數(shù)，即形成的不同的圓排列組的個數(shù)，即k-圓圓排列分劃數(shù)記為第一類排列分劃數(shù)記為第一類Stirling數(shù)，表示數(shù)，表示為為 或或S1(n,k)kn性質(zhì)性質(zhì)(1)性質(zhì)性質(zhì)(2)性質(zhì)性質(zhì)(3)性質(zhì)性質(zhì)(4)!1(1nn1nn)(0nkkn21nnn2022-3-25計算機科學與技術(shù)學院15定理定理3.5.3

4、 第一類Stirling數(shù)滿足如下遞推關(guān)系 ), 1() 1() 1, 1(),()1 (1) 1(11111knSnknSknSnkknnknkn 第一類第一類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院16證明：證明：等式左邊 是將集合的k-圓排列分劃數(shù)，這些圓排列組可以分成兩類： 第1類：an單獨構(gòu)成一個圓排列，只需對集合A-an進行(k-1)-圓排列分劃，再加上an這個圓排列，就構(gòu)成了A的k-圓排列分劃，因此，這類分劃有 個。 kn11kn第一類第一類Stirling數(shù)數(shù)2022-3-25計算機科學與技術(shù)學院17第2類： an不是A的k-圓排列分劃中的單獨一個圓排列，此時

5、，先構(gòu)造A-an的k-圓排列分劃，共有 種方法，然后對于A-an的每個k-圓排列分劃，將an插入該k-圓排列分劃的k個圓排列中的某一個圓排列中，共有n-1種不同的插入方法，因此集合A的此類k-圓排列分劃共有 個。 綜上以上分析，由加法原理，有 kn1 knn1) 1( knnknkn1) 1(112022-3-25計算機科學與技術(shù)學院18小結(jié)：小結(jié)：S2(n,k) vs. S1(n,k)nS2 (n,1)=1nS2 (n,n)=1nS2 (n,n-1)=C(n,2)nS2 (n,k)=0(kn)nS2 (n+1,k)=S2 (n,k-1)+k S2 (n,k)nS2 (n,k)的生成函數(shù)為的生

6、成函數(shù)為nS1(n,1)=(n-1)!nS1(n,n)=1nS1(n,n-1)=C(n,2)nS1 (n,k)=0(kn) nS1(n+1,k)= S1 (n,k-1)+n S1 (n,k)nS1 (n,k)的生成函數(shù)為的生成函數(shù)為P(x,n)(1)(1 2 )(1)kxxxkx2022-3-25計算機科學與技術(shù)學院19正整數(shù)的分拆正整數(shù)的分拆正整數(shù)的分拆就是將一個正整數(shù)分成幾個正整數(shù)的和，正整數(shù)的分拆就是將一個正整數(shù)分成幾個正整數(shù)的和，分拆分拆問題也是組合論的重要內(nèi)容之一問題也是組合論的重要內(nèi)容之一。 定義定義 3.6.1 正整數(shù)正整數(shù) n 的一個的一個 k 分拆是把分拆是把 n 表示成表示

7、成 k 個正個正整數(shù)的和整數(shù)的和 12(1)knnnn k（3.6.1） 的一種表示法，其中的一種表示法，其中 0(1)inik ， in叫做該分拆的分部量。叫做該分拆的分部量。 2022-3-25計算機科學與技術(shù)學院20正整數(shù)的分拆正整數(shù)的分拆2022-3-25計算機科學與技術(shù)學院21正整數(shù)的分拆正整數(shù)的分拆例如：例如： 4=2+1+1=1+2+1=1+1+2 是是 4 的所有的所有 3 個有序個有序 3 分拆， 在分拆， 在 4 的第一個有序的第一個有序 3 分拆中， 第分拆中， 第 1個分部量為個分部量為 2，第，第 2 個和第個和第 3 個分部量均為個分部量均為 1，而，而 4=2+1

8、+1 是是 4 的唯一一個的唯一一個 3（無序）分拆。（無序）分拆。 2022-3-25計算機科學與技術(shù)學院22有有 序序無無 序序不允許重復(fù)不允許重復(fù)4=4，4=1+3，4=3+14=4，4=1+3允許重復(fù)允許重復(fù)4=4，4=1+3，4=3+14=2+2，4=2+1+1，4=1+2+14=1+1+2，4=1+1+1+14=4，4=1+34=2+2，4=1+1+24=1+1+1+14的分拆正整數(shù)的分拆正整數(shù)的分拆2022-3-25計算機科學與技術(shù)學院23正整數(shù)的分拆正整數(shù)的分拆n集合的（無序）分劃集合的（無序）分劃A=a,b,c,dnA=a,bc dn =a,cb dn =a,db cn =b

9、,ca dn =b,da cn =c,da bS2(4,3)=C(4,2)=6nA=1,11 1B(4,3)=12022-3-25計算機科學與技術(shù)學院24有序分拆有序分拆 定定 理理 3.6.1 正正 整整 數(shù)數(shù) n 的的 有有 序序 k 分分 拆拆 的的 個個 數(shù)數(shù) 為為11nk。 證證 明明 正正 整整 數(shù)數(shù) n 分分 成成 k 個個 分分 部部 量量 的的 一一 個個 有有 序序 分分 拆拆 12knnnn 等等 價價 于于 方方 程程12kxxxn 的的 正正 整整 數(shù)數(shù) 解解12()knnn， 由由 3.3 節(jié)節(jié) 定定 理理 3.2.5 的的 證證 明明 知知 ， 正正整整 數(shù)數(shù) n

10、 的的 有有 序序 k 分分 拆拆 的的 個個 數(shù)數(shù) 為為11nk。 由由 定定 理理 3.2.5 和和 定定 理理 3.6.1 知知 ， 正正 整整 數(shù)數(shù) n 的的 有有 序序 k 分分 拆拆 數(shù)數(shù) 等等于于 多多 重重 集集 合合12,kMaaa 的的12,kaaa至至 少少 出出 現(xiàn)現(xiàn) 一一 次次的的 n 組組 合合 數(shù)數(shù) ， 均均 為為11nk。 2022-3-25計算機科學與技術(shù)學院25有序分拆有序分拆12knnnn12(1)(1)(1)knknnn1111nkknkk2022-3-25計算機科學與技術(shù)學院26有序分拆有序分拆定理定理 3.6.2 （1）正整數(shù)）正整數(shù) n 的有序的有

11、序 k 分拆，要求第分拆，要求第 i 的分部量大的分部量大于等于于等于ip，其個數(shù)為，其個數(shù)為111kiinkpk； 2022-3-25計算機科學與技術(shù)學院2712knnnn11221()()()kikkinpnpnpnp111kiinpkk2022-3-25計算機科學與技術(shù)學院28有序分拆有序分拆2022-3-25計算機科學與技術(shù)學院29有序分拆有序分拆反反之之，若若給給定定方方程程（3.6.4）的的一一組組非非負負整整數(shù)數(shù)解解12,ky yy，令令(1)iiinypik ，則則構(gòu)構(gòu)成成 n 的的一一個個有有序序 k 分分拆拆（3.6.2） ，且且滿滿足足條條件件（3.6.3） 。 所所以以

12、，n 的的滿滿足足條條件件（3.6.3）的的有有序序 k 分分拆拆與與方方程程（3.6.4）的的非非負負整整數(shù)數(shù)解解之之間間構(gòu)構(gòu)成成一一一一對對應(yīng)應(yīng)，由由定定理理 3.2.4 的的證證明明知知， 其其個個數(shù)數(shù)為為 111kiinkpk 2022-3-25計算機科學與技術(shù)學院30有序分拆有序分拆（2） 正正整整數(shù)數(shù) 2n 分分拆拆成成 k 個個分分部部， 各各分分部部量量都都是是正正偶偶數(shù)數(shù)的的有有序序分分拆拆個個數(shù)數(shù)為為11nk。 證證明明：設(shè)設(shè) 2n 的的一一個個有有序序 k 分分拆拆 122knxxx 滿滿足足條條件件 (1)ixik 為偶數(shù)， （3.6.5） 令令(1)2iixyik ，

13、則則有有 12knyyy， 即即12,ky yy是是 n 的的一一個個有有序序 k 分分折折。 2022-3-25計算機科學與技術(shù)學院31122/ 2(1)kiinnnnynik 12knyyy11nk正偶數(shù)：111nknkkn非負偶數(shù)：2022-3-25計算機科學與技術(shù)學院32有序分拆有序分拆 反 之 ，反 之 ，12,ky yy是是n 的 一 個 有 序的 一 個 有 序k分 拆 ， 令分 拆 ， 令2(1)iixyik ，則，則12,kx xx是是 2n 的一個滿足條件（的一個滿足條件（3.6.5）的有序的有序 k 分拆。分拆。 所以，所以，2n 滿足條件（滿足條件（3.6.5）的有序）

14、的有序 k 分拆數(shù)等于分拆數(shù)等于 n 的有序的有序k 分拆數(shù)，為分拆數(shù)，為11nk。 2022-3-25計算機科學與技術(shù)學院33有序分拆有序分拆2022-3-25計算機科學與技術(shù)學院3412(1)/ 2(1)kiinnnnynik 122knkyyy112211nknkkkk2022-3-25計算機科學與技術(shù)學院35無序分拆無序分拆我們用我們用( , )B n k來表示來表示 n 的的 k 分拆的個數(shù)，用分拆的個數(shù)，用( )B n表示表示 n 的所有的所有分拆的個數(shù)，則顯然有分拆的個數(shù)，則顯然有 （1）( , )0()B n kkn； （2）1( )( , )nkB nB n k n 的的 k

15、 分拆中，各分部量的次序無關(guān)緊要，一般按遞降順分拆中，各分部量的次序無關(guān)緊要，一般按遞降順序排列，若序排列，若12knnnn 則則12knnn 如果在如果在 n 的的 k 分拆中有分拆中有ik個分部量為個分部量為(1)iin ，那么可以把該，那么可以把該分拆記為分拆記為1212nnkkkn ， 有時也記為有時也記為121 2nkkknn 2022-3-25計算機科學與技術(shù)學院36無序分拆無序分拆例如，例如，B(9,5)=5, 9 的所有的所有 5 分拆為：分拆為： 9 = 5 + 1 + 1 + 1+ 1 = 1 5 + 4 1 = 4 + 2 + 1 + 1+ 1 = 1 4 + 1 2 +

16、 3 1 = 3 + 3 + 1 + 1 + 1 = 2 3 + 3 1 = 3 + 2 + 2 + 1 + 1 = 1 3 + 2 2 + 2 1 = 2 + 2 + 2 + 2 + 1 = 4 2 + 1 1 2022-3-25計算機科學與技術(shù)學院37無序分拆無序分拆nB(n,1)=1nB(n,n)=1nB(n,n-1)=1nB(n,2)= n/2 2022-3-25計算機科學與技術(shù)學院38無序分拆無序分拆2022-3-25計算機科學與技術(shù)學院39無序分拆無序分拆1121231231231( ,1)000( ,2)00( ,3)0( , )( )0,(1)( )( , )kkkikkiB

17、nnnB nnnnB nnnnnB n knnnnnB nnnnnnnikB nB n i 2022-3-25計算機科學與技術(shù)學院40無序分拆無序分拆11231231( + , )( , )( + , )( )( )0,(1)( + , )+(1)(1)(1)(1)(1)0,(1)( )( , )kkikkikikkiB n k kB n iB n k kB nB nnnnnnnikB n k kn knnnnnikB nB n i 證明：只需證明2022-3-25計算機科學與技術(shù)學院41無序分拆無序分拆111111( )( , )( )( , )( )( )( , )( )()kkikkik

18、kkkB nB n iBnB n iB nBnB n kBnB nk2022-3-25計算機科學與技術(shù)學院42無序分拆無序分拆111( )( , )( + , )( )( )( )( , )( )()kkikkkkkB nB n iB n k kB nB nBnB n kBnB nk2022-3-25計算機科學與技術(shù)學院43無序分拆無序分拆2022-3-25計算機科學與技術(shù)學院44分拆的分拆的FerrersFerrers圖圖2022-3-25計算機科學與技術(shù)學院45分拆的分拆的FerrersFerrers圖圖例如，例如，15 的的 4 分拆分拆 15 = 5 + 5 + 3 + 2 （3.6.

19、9） 的的 Ferrers 圖如圖圖如圖 3.6.1 所示。所示。 圖圖 3.6.1 反過來，對于反過來，對于 n 的一個的一個 Ferrers 圖，又可按上述規(guī)則對應(yīng)于圖，又可按上述規(guī)則對應(yīng)于 n的唯一的一個分拆，所以，的唯一的一個分拆，所以，n 的分拆同它的的分拆同它的 Ferrers 圖之圖之間是間是一一對應(yīng)的。一一對應(yīng)的。 2022-3-25計算機科學與技術(shù)學院46分拆的分拆的FerrersFerrers圖圖2022-3-25計算機科學與技術(shù)學院47分拆的分拆的FerrersFerrers圖圖從分拆的從分拆的 Ferrers 圖可以證明以下一些定理：圖可以證明以下一些定理： 定理定理

20、3.6.4 n 的的 k 分拆的個數(shù)等于分拆的個數(shù)等于 n 的最大分部量為的最大分部量為 k 的的分拆數(shù)。分拆數(shù)。 證明證明 上面定義的分拆的共軛運算是一個映射，它將上面定義的分拆的共軛運算是一個映射，它將 n 的的最大分部量為最大分部量為 k 的分拆映射到的分拆映射到 n 的的 k 分拆，例如，分拆（分拆，例如，分拆（3.6.9）是是 15 的最大分部最為的最大分部最為 5 的分拆，其共軛分拆（的分拆，其共軛分拆（3.6.10）是）是 15 的的一個一個 5 分拆，并全這個映射顯然是一一的，所以兩者相等。分拆，并全這個映射顯然是一一的，所以兩者相等。 2022-3-25計算機科學與技術(shù)學院4

21、8分拆的分拆的FerrersFerrers圖圖定理定理 3.6.5 n 的自共軛分拆的個數(shù)等于的自共軛分拆的個數(shù)等于 n 的各分部量都是奇數(shù)的各分部量都是奇數(shù)且兩兩不等的分拆的個數(shù)。且兩兩不等的分拆的個數(shù)。 證明證明 為了證明這個性質(zhì)，我們將借助于為了證明這個性質(zhì)，我們將借助于 Ferrers 圖建立圖建立一個一個 n 的各分部量為奇數(shù)且兩兩不等的分拆到的各分部量為奇數(shù)且兩兩不等的分拆到 n 的自軛分拆之的自軛分拆之間的一一對應(yīng)。間的一一對應(yīng)。 設(shè)設(shè) n 的一個分部量為奇數(shù)且兩兩不等的分拆為的一個分部量為奇數(shù)且兩兩不等的分拆為 12(21)(21)(21)knnnn， （3.6.11） 其中其

22、中 120knnn 2022-3-25計算機科學與技術(shù)學院49分拆的分拆的FerrersFerrers圖圖由由 n 的分拆 （的分拆 （3.6.11） ，） ， 我們構(gòu)造我們構(gòu)造 n 的一個自共軛分拆的的一個自共軛分拆的 Ferrers圖。圖。在第在第 1 行與第行與第 1 列都畫列都畫11n 個點，共有個點，共有121n 個點；畫完個點；畫完第第1行和第行和第1列后， 在第列后， 在第2行與第行與第2列再各畫列再各畫21n 個點， 共個點， 共221n 個點；在第個點；在第 k 行與第行與第 k 列再畫列再畫1kn 個點，共個點，共21kn 個點，個點，因為因為12knnn， 所以如此畫出的

23、， 所以如此畫出的 n 個點的點陣圖的每一行個點的點陣圖的每一行都不比下一行的點數(shù)少，因而是都不比下一行的點數(shù)少，因而是 n 的一個分拆的的一個分拆的 Ferrers 圖，圖，且由上面的構(gòu)造法知，該且由上面的構(gòu)造法知，該 Ferrers 圖是對稱的，所以其對應(yīng)的圖是對稱的，所以其對應(yīng)的分拆是自共軛的。分拆是自共軛的。 2022-3-25計算機科學與技術(shù)學院50分拆的分拆的FerrersFerrers圖圖例例如如，且且上上述述方方法法由由分分折折 17 = 9 + 5 + 3 =（24 + 1）+（32 + 1）+（21 + 1） 構(gòu)構(gòu)造造的的 Ferrers 圖圖如如下下圖圖所所示示，對對應(yīng)應(yīng)

24、的的自自共共軛軛分分拆拆為為 17=5+4+4+3+1 顯顯然然，上上面面建建立立的的 n 的的分分部部量量為為奇奇數(shù)數(shù)且且兩兩兩兩不不等等的的分分拆拆與與 n 的的自自共共軛軛分分拆拆之之間間的的對對應(yīng)應(yīng)關(guān)關(guān)系系是是一一一一的的，所所以以定定理理的的結(jié)結(jié)論論成成立立。 + + + + = = 2022-3-25計算機科學與技術(shù)學院51分拆的分拆的FerrersFerrers圖圖定定理理 3.6.6 n 的的分分部部量量兩兩兩兩不不等等的的分分拆拆的的個個數(shù)數(shù)等等于于 n 的的各各分分部部量量都都是是奇奇數(shù)數(shù)的的分分拆拆的的個個數(shù)數(shù)。 證證明明 證證明明的的方方法法還還是是建建立立定定理理中中

25、提提及及的的兩兩類類不不同同的的分分拆拆之之間間的的一一一一對對應(yīng)應(yīng)。 在在一一個個 n 的的各各分分部部量量為為奇奇數(shù)數(shù)的的分分拆拆中中，假假設(shè)設(shè)數(shù)數(shù) 2k+1 出出現(xiàn)現(xiàn) p次次，我我們們將將 p 寫寫成成 2 的的冪冪次次和和的的形形式式： 121222()iipii， 則則這這種種表表示示法法是是唯唯一一的的， 我我們們將將 n 的的這這個個分分拆拆的的 Ferrers 圖圖中中這這(21)pk個個 小小 點點 按按 下下 列列 方方 法法 重重 排排 ： 各各 行行 的的 小小 點點 數(shù)數(shù) 分分 別別 為為12(21) 2 ,(21) 2 ,iikk，如如此此將將原原來來那那個個分分拆

26、拆的的 Ferrers 圖圖中中所所有有的的點點重重排排了了一一次次，然然后后再再將將各各行行按按小小點點數(shù)數(shù)遞遞減減的的順順序序排排列列，就就得得到到 n 的的另另一一個個分分拆拆的的 Ferrers 圖圖。 2022-3-25計算機科學與技術(shù)學院52分拆的分拆的FerrersFerrers圖圖例例如如，分分拆拆 24 = 25 + 33 + 51 的的 Ferrers 圖圖如如圖圖 3.6.4 所所示示，我我們們將將重重復(fù)復(fù)數(shù)數(shù) 2，3，5 分分別別寫寫成成 2的的冪冪次次和和的的形形式式： 2 = 21， 3 = 21 + 20， 5 = 22 + 20， 則則由由上上述述方方法法構(gòu)構(gòu)造

27、造出出的的新新 Ferrers 圖圖如如圖圖 3.6.5 所所示示， 它它所所對對應(yīng)應(yīng)的的24 的的分分拆拆為為 24 = 10 + 6 + 4 + 3 + 1 在在新新的的 Ferrers 圖圖中中，各各行行的的點點數(shù)數(shù)為為(21) 2ik 的的形形式式，在在各各行行點點數(shù)數(shù)的的表表達達式式(21) 2ik 中中，參參數(shù)數(shù) k 和和 i 中中必必有有一一個個不不同同，所所以以各各行行的的點點數(shù)數(shù)互互不不相相同同，因因而而它它所所對對應(yīng)應(yīng)的的分分拆拆的的各各分分部部量量不不同同。 2022-3-25計算機科學與技術(shù)學院53分拆的分拆的FerrersFerrers圖圖12121122121111

28、2111(21)(21)(21)2(21)2(21)2(21)2 (21)2 (21)2 (21)2 (21)tkkktkkkttmmmiiitkkkmmmiiitkkklnpnpnpnnnnnnnn12122 (21)2 (21)(21)2(21)nnnn 不妨設(shè)2022-3-25計算機科學與技術(shù)學院54分拆的分拆的FerrersFerrers圖圖 12510 1236 0233 2214 0211 圖圖 3.6.4 2022-3-25計算機科學與技術(shù)學院55分拆的分拆的FerrersFerrers圖圖 圖圖 3.6.5 如如上上建建立立了了兩兩類類分分拆拆之之間間的的一一一一對對應(yīng)應(yīng)，事事

29、實實上上，任任一一自自然然數(shù)數(shù)表表示示成成 2 2 的的冪冪次次和和的的形形式式是是唯唯一一的的，從從而而上上面面建建立立的的映映射射是是單單射射，另另外外，上上面面構(gòu)構(gòu)造造新新的的 F Fe er rr re er rs s 圖圖的的方方法法顯顯然然是是可可逆逆的的，所所以以上上面面的的映映射射是是滿滿射射。 綜綜合合以以上上分分析析，n 的的分分部部量量兩兩兩兩不不等等的的分分拆拆的的個個數(shù)數(shù)等等于于 n 的的分分部部量量都都是是奇奇數(shù)數(shù)的的分分拆拆的的個個數(shù)數(shù)。 2022-3-25計算機科學與技術(shù)學院56小結(jié)：小結(jié)：S2(n,k) vs. B(n,k)nS2 (n,1)=1nS2 (n,

30、n)=1nS2 (n,n-1)=C(n,2)nS2 (n,2)=2n-1-1nS2 (n+1,k)=S2 (n,k-1)+k S2 (n,k)n有序分劃有序分劃k! S2 (n,k)nS2 (n,k)有顯示表達式有顯示表達式nB(n,1)=1nB(n,n)=1nB(n,n-1)=1nB(n,2)= n/2 nB(n+k,k)=B(n,1)+ B(n,2) + B(n,3)+B(n,k)n有序分拆有序分拆C(n-1,k-1)nB(n,k)無顯示表達式無顯示表達式201( , )( 1)()!kinikS n kkiik 2022-3-25計算機科學與技術(shù)學院57小結(jié)小結(jié)不允許為空不允許為空 允許為空允許為空有序分劃有序分劃 k!S2(n,k)kn無序分劃無序分劃 S2(n,k)有序分拆有序分拆無序分拆無序分拆 B(n,k)21( , )kiS n i1( , )( )kkiB n iB n11nk1nkn2022-3-25計算機科學與技術(shù)學院58分