組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分

1、組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分1第第2章章 遞推關系與母函數(shù)遞推關系與母函數(shù) 2.1 2.1 遞推關系遞推關系 2.2 2.2 母函數(shù)母函數(shù)()() 2.3 Fibonacci 2.3 Fibonacci數(shù)列數(shù)列 2.4 2.4 優(yōu)選法與優(yōu)選法與FibonacciFibonacci序列的應用序列的應用 2.5 2.5 母函數(shù)的性質母函數(shù)的性質 2.6 2.6 線性常系數(shù)齊次遞推關系線性常系數(shù)齊次遞推關系 2.7 2.7 關于常系數(shù)非齊次遞推關系關于常系數(shù)非齊次遞推關系 2.8 2.8 整數(shù)的拆分整數(shù)的拆分 2.9 ferrers2.9 ferrers圖像圖像 2.10 2.10 拆分數(shù)估計

2、拆分數(shù)估計 2.11 2.11 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 2.12 2.12 廣義二項式定理廣義二項式定理 2.13 2.13 2.14 2.14 非線性遞推關系舉例非線性遞推關系舉例 2.15 2.15 遞推關系解法的補充遞推關系解法的補充組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分22.8：整數(shù)的拆分：整數(shù)的拆分 1 1、拆分的概念、拆分的概念 2 2、拆分的模型、拆分的模型 3 3、拆分算法、拆分算法: :遞歸實現(xiàn)遞歸實現(xiàn) 4 4、用母函數(shù)討論拆分數(shù)、用母函數(shù)討論拆分數(shù)組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分32.8：整數(shù)的拆分：整數(shù)的拆分 所謂整數(shù)的拆分，是指把一個正整所謂整數(shù)的拆分，是指把一個正整數(shù)

3、拆分成若干正整數(shù)的和。不同的拆分數(shù)拆分成若干正整數(shù)的和。不同的拆分法的數(shù)目稱為拆分數(shù)法的數(shù)目稱為拆分數(shù)例如：考慮正整數(shù)例如：考慮正整數(shù)4 4的拆分數(shù)：的拆分數(shù)：4=44=4，4=3+14=3+1，4=2+24=2+2，4=2+1+14=2+1+1，4=1+1+1+14=1+1+1+1 通常用通常用p(n)p(n)表示整數(shù)表示整數(shù)n n拆分成若干拆分成若干正整數(shù)的和的拆分數(shù)，也可說成方案正整數(shù)的和的拆分數(shù)，也可說成方案數(shù)數(shù) 例如例如p(4)=5p(4)=5。 1 1、拆分的概念拆分的概念組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分4(1)(1)、C(n,r)C(n,r) 2 2、拆分的模型拆分的模型2.8

4、：整數(shù)的拆分：整數(shù)的拆分 從從n n個不同的球中取出個不同的球中取出r r個個, ,放進放進r r個相同的個相同的盒子中盒子中, ,不許空盒不許空盒, ,有多少種放法有多少種放法. .(2)(2)、P(n,r)P(n,r) 從從n n個不同的球中取出個不同的球中取出r r個個, ,放進放進r r個不相同個不相同的盒子中的盒子中, ,不許空盒不許空盒, ,有多少種放法有多少種放法. .組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分5(3)(3)、從、從n n個不同元素中取個不同元素中取r r個允許重復的組合個允許重復的組合2.8：整數(shù)的拆分：整數(shù)的拆分 r r個相同的球放進個相同的球放進n n個不同的盒子中

5、個不同的盒子中, ,允許允許空盒空盒, ,有多少種放法有多少種放法. . 以正整數(shù)以正整數(shù)4 4為例：為例： 4=44=4，4=3+14=3+1，4=2+24=2+2，4=2+1+14=2+1+1，4=1+1+1+14=1+1+1+1(4)(4)、正整數(shù)、正整數(shù)n n的拆分數(shù)的拆分數(shù)組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分6 正整數(shù)正整數(shù)n n的拆分，相當于把的拆分，相當于把n n個無區(qū)別個無區(qū)別的球放進的球放進n n個無區(qū)別的盒子，盒子中允許放個無區(qū)別的盒子，盒子中允許放一個以上的球，也允許空著一個以上的球，也允許空著 以正整數(shù)以正整數(shù)4 4為例，球的放法如下：為例，球的放法如下： 4=44=4，

6、4=3+14=3+1，4=2+24=2+2，4=2+1+14=2+1+1，4=1+1+1+14=1+1+1+1 2.8：整數(shù)的拆分：整數(shù)的拆分*組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分7 3 3、拆分算法、拆分算法: :遞歸實現(xiàn)遞歸實現(xiàn) 定義一個函數(shù)定義一個函數(shù)Q(n,m)Q(n,m)：表示整數(shù)：表示整數(shù)n n的所有加的所有加數(shù)都不超過數(shù)都不超過m m的拆分數(shù)。的拆分數(shù)。 n n的拆分數(shù)就可以表示為的拆分數(shù)就可以表示為Q(n,n)Q(n,n)Q(n,n)Q(n,n)有以下遞歸關系有以下遞歸關系(1)Q(n,n)=1+Q(n,n-1)(1)Q(n,n)=1+Q(n,n-1)停止條件：停止條件：(1)Q

7、(n,1)=1(1)Q(n,1)=1(2)Q(1,m)=1(2)Q(1,m)=12.8：整數(shù)的拆分：整數(shù)的拆分Q(n,m)Q(n,m)有以下遞歸關系有以下遞歸關系 (2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (2)Q(n,m)=Q(n,m-1)+Q(n-m,m)組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分8 int divinteger(int n,int m) int divinteger(int n,int m) if (n1|m1) if (n1|m1) printf( printf(“errorerror”);); else if(n=1|m=1) else if(n=1|m=1)

8、return(1); return(1); else if(nm) else if(nm) return divinteger(n,n) return divinteger(n,n) else if(n=m) else if(n=m) return(1+divinter(n,n-1); return(1+divinter(n,n-1); else else return(divinteger(n,m-1)+divinteger(n-m,m);return(divinteger(n,m-1)+divinteger(n-m,m); 2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分9

9、 例例1 1 求求4 4的拆分數(shù)。的拆分數(shù)。 解：分析下面的多項式解：分析下面的多項式x x4 4項的系數(shù)項的系數(shù)與與4 4的拆分數(shù)的關系的拆分數(shù)的關系. . (1+x+x (1+x+x2 2+x+x3 3+x+x4 4)(1+x)(1+x2 2+x+x4 4) )(1+x(1+x3 3)(1+x)(1+x4 4) ) 4 4、用母函數(shù)討論拆分數(shù)、用母函數(shù)討論拆分數(shù)2.8：整數(shù)的拆分：整數(shù)的拆分4=1+1+1+1,4=2+1+14=1+1+1+1,4=2+1+1，4=2+24=2+2，4=3+14=3+1， 4=44=4，組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分10 n n的拆分數(shù)的母函數(shù)。的拆分數(shù)

10、的母函數(shù)。 4 4、用母函數(shù)討論拆分數(shù)、用母函數(shù)討論拆分數(shù).12xx.142xx.163xx.nxxxx11.111111322.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分11 例例2 2 求求1 1角、角、2 2角、角、3 3角的郵票可貼角的郵票可貼出不同數(shù)值郵資的方案數(shù)的母函數(shù)。出不同數(shù)值郵資的方案數(shù)的母函數(shù)。 解：解： 單獨用單獨用1 1角的母函數(shù)為角的母函數(shù)為1+x+x1+x+x2 2+x+x3 3+ + 單獨用單獨用2 2角郵票的母函數(shù)為角郵票的母函數(shù)為1+x1+x2 2+x+x4 4+x+x6 6+ + 單獨用單獨用3 3角郵票的母函數(shù)為角郵票的母函數(shù)為1+x1+

11、x3 3+x+x6 6+x+x9 9+ +2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分12.)1.)(1.)(1 ()(63422xxxxxxxG)1)(1)(1 (132xxx.543215432xxxxx2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分13 例例3 3 求正整數(shù)求正整數(shù)n n拆分成拆分成1,2,1,2,m m的和，的和，并允許重復的拆分數(shù)。如若其中并允許重復的拆分數(shù)。如若其中m m至少出現(xiàn)至少出現(xiàn)一次，試求它的方案數(shù)及其母函數(shù)。一次，試求它的方案數(shù)及其母函數(shù)。 解解1 1：)1).(1)(1 (12mxxx展開式中展開式中xn項的系數(shù)就是

12、要求的拆分數(shù)。項的系數(shù)就是要求的拆分數(shù)。2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分14 解解2 2：如果：如果m m至少出現(xiàn)一次。至少出現(xiàn)一次。)1).(1)(1 (2mmxxxx)1).(1)(1()1(12mmxxxx)1).(1)(1 (1)1).(1)(1 (1122mmxxxxxxG(x)=(1+x+x2+ )(1+x2+x4+ )(xm+x2m+)2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分152.8：整數(shù)的拆分：整數(shù)的拆分 正整數(shù)正整數(shù)n n拆分成拆分成1,2,1,2,m m的和，并允許的和，并允許重復的拆分數(shù)。重復的拆分數(shù)。 若其中若其

13、中m m至少出現(xiàn)一次，它的方案數(shù)等至少出現(xiàn)一次，它的方案數(shù)等于拆分成于拆分成1,2,1,2,m,m的拆分數(shù)減去拆分成的拆分數(shù)減去拆分成1,2,1,2,m-1,m-1的拆分數(shù)。的拆分數(shù)。 以正整數(shù)以正整數(shù)4 4為例：為例： 4=44=4，4=3+14=3+1，4=2+24=2+2，4=2+1+14=2+1+1，4=1+1+1+14=1+1+1+1組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分16 定理定理2.8.1 2.8.1 正整數(shù)正整數(shù)r r拆分成不同正整數(shù)和的拆拆分成不同正整數(shù)和的拆分數(shù)，等于拆分成奇正整數(shù)的拆分數(shù)？分數(shù)，等于拆分成奇正整數(shù)的拆分數(shù)？ 對比對比7 7拆分成不同正整數(shù)之和的拆分數(shù)和拆分成

14、不同正整數(shù)之和的拆分數(shù)和拆分成奇數(shù)和的拆分數(shù)。拆分成奇數(shù)和的拆分數(shù)。 解：解：7 7拆分成不同正整數(shù)和的所有形式如下：拆分成不同正整數(shù)和的所有形式如下： 7，6+1，5+2，4+3，4+2+1共共5種種 解：解：7 7拆分成奇數(shù)和的所有形式如下：拆分成奇數(shù)和的所有形式如下： 7，5+1+1， 3+3+1， 3+1+1+1+1， 1+1+1+1+1+1+1也是也是5種種2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分17 解：首先構造解：首先構造r r拆分成不同正整數(shù)和的拆分成不同正整數(shù)和的拆分序列的母函數(shù)：拆分序列的母函數(shù)： G(x)=(1+x) (1+x2) (1+x3) (

15、1+x4) xx112).1)(1)(1 (153xxx.).1.)(1 (632xxxx.11.24xx.11.114836xxxx2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分18 定理定理2.8.2 n2.8.2 n拆分成其它數(shù)之和但重拆分成其它數(shù)之和但重復數(shù)不超過復數(shù)不超過2 2。其拆分數(shù)等于它拆分成不。其拆分數(shù)等于它拆分成不被被3 3除盡的數(shù)的和的拆分數(shù)。除盡的數(shù)的和的拆分數(shù)?？紤]考慮n=5n=5的情況的情況5 5的所有拆分情況如下：的所有拆分情況如下：5 5，4+14+1，3+23+2，3+1+13+1+1，2+2+12+2+1，2+1+1+12+1+1+1，1+

16、1+1+1+11+1+1+1+15 5，4+14+1，3+23+2，3+1+13+1+1，2+2+12+2+15 5，4+14+1，2+2+12+2+1，2+1+1+12+1+1+1，1+1+1+1+11+1+1+1+12.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分19 解：解：n n拆分成重復數(shù)不超過拆分成重復數(shù)不超過2 2的數(shù)之和的拆分數(shù)，的數(shù)之和的拆分數(shù)，其母函數(shù)為：其母函數(shù)為：.11.11.11.11)(41239263xxxxxxxxxG).1)(1)(1 (142xxx)1)(1 ()1 (23xxxxG(x)=(1+x +x2) (1+x2 +x4) (1+x3

17、 +x6) (1+x4 +x8) 2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分20 例例2-25 n2-25 n個完全相同的球放到個完全相同的球放到m m個無區(qū)個無區(qū)別的盒子，不允許空盒，問共有多少種不別的盒子，不允許空盒，問共有多少種不同的方案？其中同的方案？其中mnmn。 解：從解：從n n中取中取m m個球一個盒子放一個。個球一個盒子放一個。 整數(shù)整數(shù)n-mn-m用不超過用不超過m m的數(shù)來拆分的拆分的數(shù)來拆分的拆分數(shù)。數(shù)。)1).(1)(1 (12mxxx展開中展開中x xn-mn-m項的系數(shù)項的系數(shù)2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分2

18、1 例例6 n6 n個完全相同的球放到個完全相同的球放到m m個有區(qū)別個有區(qū)別的盒子，允許空盒，問共有多少種不同的的盒子，允許空盒，問共有多少種不同的方案？其中方案？其中mnmn。 解：第一盒，用解：第一盒，用1 1代表不放球，用代表不放球，用x x代表代表放一個球，用放一個球，用x2代表放兩個球，代表放兩個球，。單獨第。單獨第一盒的母函數(shù)可構造為：一盒的母函數(shù)可構造為：1+1+x+x2+ +xn+其它盒也有同樣的情況，共其它盒也有同樣的情況，共m m個盒子。個盒子。盒第第二盒第一盒m .)1.).(1.)(1 ()(222xxxxxxxG2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)

19、整數(shù)的拆分22 例例7 n7 n個完全相同的球放到個完全相同的球放到m m個有區(qū)別個有區(qū)別的盒子，不允許空盒，問共有多少種不同的盒子，不允許空盒，問共有多少種不同的方案？其中的方案？其中mnmn。 解：第一盒，用解：第一盒，用1 1代表不放球，用代表不放球，用x x代代表放一個球，用表放一個球，用x2代表放兩個球，代表放兩個球，。因。因為不允許空盒，因此常數(shù)項為零，單獨第為不允許空盒，因此常數(shù)項為零，單獨第一盒的母函數(shù)可構造為：一盒的母函數(shù)可構造為：x+x2+ +xn+其它盒也有同樣的情況，共其它盒也有同樣的情況，共m m個盒子。個盒子。盒第第二盒第一盒m .).).(.)()(222xxxx

20、xxxG2.8：整數(shù)的拆分：整數(shù)的拆分組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分23mmxx)1( .), 1(.! 2) 1(1 (2kmxkkmCxmmmxx xn-m項的系數(shù)是項的系數(shù)是: : C(m+n-m-1,n-m)=C(n-1,n-m)=C(n-1,m-1) 因此。方案數(shù)為因此。方案數(shù)為C(n-1,m-1)2.8：整數(shù)的拆分：整數(shù)的拆分*組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分242.9 費勒斯（費勒斯（Ferrers)圖像圖像 假設正整數(shù)假設正整數(shù)n n拆分成拆分成n=n1+n2+nk。 其中其中n n1nn2 nn3 n nk。將他們排成階。將他們排成階梯形，左邊對齊，第一行梯形，左邊對齊

21、，第一行n n1格，第二行格，第二行n n2格，格，第第k k行行n nk格。格。32211234例如：例如：8=3+2+2+18=3+2+2+11 1、什么是費勒斯圖像、什么是費勒斯圖像組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分252 2、費勒斯（費勒斯（Ferres)Ferres)圖像的性質：圖像的性質：(1)(1)每一層至少有一個格子；每一層至少有一個格子； (3)(3)行與列互換，即第行與列互換，即第1 1行與第行與第1 1列互換，列互換，第第2 2行與第行與第2 2列互換，列互換，, ,也就是沿對角線旋也就是沿對角線旋轉轉180180，仍然是費勒斯圖像；，仍然是費勒斯圖像； 后一個費勒斯圖像

22、稱為前一個費勒斯后一個費勒斯圖像稱為前一個費勒斯圖像的共軛圖像，而且互為共軛。圖像的共軛圖像，而且互為共軛。2.9 費勒斯（費勒斯（Ferrers)圖像圖像 (2) (2)下一層的格數(shù)不多于上一層的格子下一層的格數(shù)不多于上一層的格子數(shù)；數(shù)； 組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分262.9 費勒斯（費勒斯（Ferrers)圖像圖像322112343、費勒斯圖像對拆分數(shù)的討論、費勒斯圖像對拆分數(shù)的討論例如：例如：8=3+2+2+18=3+2+2+1組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分27定理定理2.9.1 2.9.1 如下兩種拆分方式的數(shù)的是相等的。如下兩種拆分方式的數(shù)的是相等的。(1)(1)把正整數(shù)

23、把正整數(shù)n n拆分成拆分成m m個數(shù)的和的拆分數(shù)。個數(shù)的和的拆分數(shù)。(2)(2)把正整數(shù)把正整數(shù)n n拆分成最大數(shù)為拆分成最大數(shù)為m m的拆分數(shù)之和。的拆分數(shù)之和。推論推論: :如下拆分數(shù)相同如下拆分數(shù)相同(1)(1)正整數(shù)正整數(shù)n n拆分成最多不超過拆分成最多不超過m m個數(shù)的和的個數(shù)的和的拆分數(shù)，拆分數(shù)，(2)(2)正整數(shù)正整數(shù)n n拆分成最大數(shù)不超過拆分成最大數(shù)不超過m m的數(shù)的拆的數(shù)的拆分數(shù)。分數(shù)。2.9 費勒斯（費勒斯（Ferrers)圖像圖像組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分28定理定理2.9.1 2.9.1 如下兩種拆分方式的數(shù)的是相等的。如下兩種拆分方式的數(shù)的是相等的。(1)(

24、1)把正整數(shù)把正整數(shù)n n拆分成拆分成m m個數(shù)的和的拆分數(shù)。個數(shù)的和的拆分數(shù)。(2)(2)把正整數(shù)把正整數(shù)n n拆分成最大數(shù)為拆分成最大數(shù)為m m的拆分數(shù)之和。的拆分數(shù)之和。.12xx.142xx.163xx.mmxxxxx1.11111132.32mmmxxx2.9 費勒斯（費勒斯（Ferrers)圖像圖像組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分29.12xx.142xx.163xx.mxxxx11.11111132.132mmmxxx推論推論: :正整數(shù)正整數(shù)n n拆分成最多不超過拆分成最多不超過m m個數(shù)的和個數(shù)的和的拆分數(shù)，等于將的拆分數(shù)，等于將n n拆分成最大數(shù)不超過拆分成最大數(shù)不超過m

25、 m的的數(shù)的拆分數(shù)。數(shù)的拆分數(shù)。2.9 費勒斯（費勒斯（Ferrers)圖像圖像組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分30mxxxx11.11111132拆分成正好拆分成正好m m個數(shù)的拆分數(shù)。個數(shù)的拆分數(shù)。mmxxxxx1.11111132拆分成不超拆分成不超m m個數(shù)的拆分數(shù)。個數(shù)的拆分數(shù)。拆分成不超拆分成不超m-1m-1個數(shù)的拆分數(shù)。個數(shù)的拆分數(shù)。13211.111111mxxxx2.9 費勒斯（費勒斯（Ferrers)圖像圖像組合數(shù)學課件第二章第四節(jié)整數(shù)的拆分31 定理定理2.9.2 2.9.2 整數(shù)整數(shù)n n拆分成互不相同的若干拆分成互不相同的若干奇數(shù)和的拆分數(shù)，與奇數(shù)和的拆分數(shù)，與n n拆分成有自共軛費勒斯拆分成有自共軛費勒斯圖像的拆分數(shù)相等。這里所講的自共軛費勒圖像的拆分數(shù)相等。這里所講的自共