組合數(shù)學(xué)(24)

1、1第八章第八章 特殊計數(shù)序列特殊計數(shù)序列8.3 分拆數(shù)分拆數(shù) 所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和和，各部分不允許出現(xiàn)，各部分不允許出現(xiàn)0值值, 本次課我們將討論本次課我們將討論對整數(shù)對整數(shù)n的進行兩類拆分的組合記數(shù)問題，一類的進行兩類拆分的組合記數(shù)問題，一類是無限制地拆分，另一類是限制拆分塊數(shù)量的是無限制地拆分，另一類是限制拆分塊數(shù)量的拆分。把整數(shù)拆分成若干整數(shù)的和，辦法不一，拆分。把整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做不同拆分法的總數(shù)叫做拆分數(shù)拆分數(shù)(或者或者分拆數(shù)分拆數(shù))。2 設(shè)設(shè)n是一個正整數(shù)，若存在正整數(shù)的集合是一個正整數(shù)，若存

2、在正整數(shù)的集合 n1, n2, nk (其中其中1 k n，ni n)使得使得 n1 n2nkn則稱則稱 n1, n2, nk 是是n的一個的一個分拆分拆。分拆個數(shù)可以記為。分拆個數(shù)可以記為Pnk 如果如果n的一個分拆含有的一個分拆含有an個個n, an-1個個(n-1),a2個個2和和a1個個1。即。即: nnan + (n-1)an-1 + + 2a2 + 1a13則將該分拆則將該分拆 記作記作: 上述表示方法僅僅是個記號上述表示方法僅僅是個記號, 沒有指數(shù)運沒有指數(shù)運算的意義。算的意義。例如：例如：整數(shù)整數(shù)n 拆分方式拆分方式 拆分個數(shù)拆分個數(shù)Pnk 2， 2, 1+1 2個個 3, 3

3、, 2+1, 1+1+1 3個個 4, 4, 3+1, 2+2, 2+1+1, 1+1+1+1 5個個12112.) 1(aaaannnn4取整數(shù)取整數(shù)4來更換表示形式：它可以是來更換表示形式：它可以是1個個4；一一個個3和一個和一個1；兩個兩個2；一個；一個2和兩個和兩個1；四個四個1。這樣，整數(shù)這樣，整數(shù)4的分拆個數(shù)：的分拆個數(shù)： Pn1=P43=P44=1 ； P42= 2共計為共計為5 ； 同時同時4的分拆可以記為：的分拆可以記為： 41, 3111, 22, 2112, 14注意注意pn與與Pnk是兩個不同概念的分拆數(shù)，是兩個不同概念的分拆數(shù)， pn表示表示正整數(shù)正整數(shù)n的分拆數(shù)，沒

4、有限制分拆的分拆數(shù)，沒有限制分拆n后各類的后各類的數(shù)量；數(shù)量； Pnk表示分拆表示分拆n后各類的數(shù)量必須是后各類的數(shù)量必須是k個個5例如：將例如：將5分拆：分拆： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1， 1+1+1+1+1，共，共7個分拆，所以：個分拆，所以： pn=7而而Pnk 根據(jù)根據(jù)k值來分：值來分： k=1,2,3,.5;故分別有：故分別有： Pn1=1; Pn2=2; Pn3=2; Pn4=1; Pn5=1;令令pn表示正整數(shù)表示正整數(shù)n的總分拆數(shù)，為了方便起見，的總分拆數(shù)，為了方便起見， 把初值：把初值： p0 = 1 ，分拆數(shù)構(gòu)成的序列為：，分拆數(shù)

5、構(gòu)成的序列為： p0, p1, p2, p3, pn,. 6由前面的討論我們已經(jīng)有：由前面的討論我們已經(jīng)有： p0 = 1, p1 = 1, p2 = 2, p3 = 3, p4 = 5, 對上述序列我們討論遞推關(guān)系。對上述序列我們討論遞推關(guān)系。定理：定理：n分拆數(shù)分拆數(shù)Pnk滿足下列遞推關(guān)系：滿足下列遞推關(guān)系：證明：只證第一式，第二式表示將證明：只證第一式，第二式表示將n分拆成分拆成1個個部分和部分和n個部分，顯然只有一種可能。個部分，顯然只有一種可能。設(shè)設(shè)E是將是將n分成不多于分成不多于k個類的分拆的集合。個類的分拆的集合。1,11nnkjnkknjnPPPP7 屬于屬于E的每個分拆可看成

6、是一個的每個分拆可看成是一個k元組元組(其分量其分量 用用0補足補足k位位)。在。在E上定義映射上定義映射: (a)=a 。 a=(a1, a2, , am, 0, 0, , 0) a =(a1+1, a2+1, , am+1, 1, 1, , 1) 在此映射下，在此映射下，E被映入將被映入將n+k分成恰有分成恰有k個個類的分拆的集合類的分拆的集合E 。因此。因此:,) 1 (21212121aaEaaaaEaa8（2） 對對a E aE 使使 (a)=a 可見可見, 為一雙射函數(shù)。因此：為一雙射函數(shù)。因此： 注意到注意到 jn時有時有Pnj=0, 故對故對kn 有：有：利用定理給出的公式，可

7、遞歸地推算利用定理給出的公式，可遞歸地推算Pnk如下：如下：kknkjjnPEPE| |1njjnkknPP19Pnk k=1 2 3 4 5 6 7 8n=1 1 2 1 1 3 1 1 1 4 1 2 1 1 5 1 2 2 1 1 6 1 3 3 2 1 1 7 1 3 4 3 2 1 1 8 1 4 5 5 3 2 1 1 10 求拆分三角的算法求拆分三角的算法: 1 定義數(shù)組定義數(shù)組P=(1：n, 1：n);2 對對k=1, n, 做做 P(k, 1) 1; P(k, k) 1;3 打印打印P（1， 1）；）； 打印打印P（2， 1），）， P（2， 2）；）；4 對對i=3, n,

8、 做做 11 4.1 對對j=2, i-1, 做做 S 0; n1i-j; n2 min(j, n1); 對對t=1, n2, SS+P(n1, t); P(i, j)S; 4.2 對對j=2, i，做，做 按行打印按行打印P(i, j)； 5結(jié)束。結(jié)束。12觀察公式：觀察公式： pn等價于方程等價于方程:nan+(n-1)an-1+.+2a2+1a1=n的非負整數(shù)解的非負整數(shù)解 an,an-1,.,a2,a1的個數(shù)。的個數(shù)。令令為為n的分拆：的分拆： 及及 a1a2a3ak1 12112.) 1(aaaannnnknnan1例如：例如：10=10=9+1=8+2=8+1+1=7+3=7+2+

9、1=7+1+1+1=6+4=6+3+1=6+2+2=6+2+1+1=6+1+1+1+1=5+5=5+4+1=5+.13 由上面的例子看出，可以對分拆著兩類化分：由上面的例子看出，可以對分拆著兩類化分： 第一類型：以分拆成的各類數(shù)量為拆分標(biāo)第一類型：以分拆成的各類數(shù)量為拆分標(biāo)準(zhǔn)；準(zhǔn)； 第二類型：以分拆成的各類中最大的數(shù)為第二類型：以分拆成的各類中最大的數(shù)為拆分標(biāo)準(zhǔn)；拆分標(biāo)準(zhǔn)； 顯然，拆分類中最大類的數(shù)越大，該類的數(shù)顯然，拆分類中最大類的數(shù)越大，該類的數(shù)量就越少：將量就越少：將10分拆為分拆為9+1只有兩類，而：只有兩類，而： 10=2+1+1+1+1+1+1+1+1就有就有9類。類。14 我們把

10、我們把的的Ferrers圖簡單稱為圖簡單稱為圖圖。它是一個左。它是一個左 齊調(diào)整點組，該組有齊調(diào)整點組，該組有k行，第行，第i行有行有ni的點。的點。 例例:10的分拆的分拆 1042211可記作可記作 412212該分拆的圖為該分拆的圖為 : . . . . . . . . . . . . . . . . . . . .顯然顯然.對于任何正整數(shù)對于任何正整數(shù)n,它的它的每個分拆可以由圖唯一確定。每個分拆可以由圖唯一確定。如如10的分拆是的分拆是4221時，時，圖為圖為：15 將將的圖看成一個矩陣的圖看成一個矩陣,這個矩陣的轉(zhuǎn)置矩陣這個矩陣的轉(zhuǎn)置矩陣 稱其為分拆稱其為分拆的共軛分拆的共軛分拆,

11、記為記為*。 *的圖與的圖與的圖互稱為的圖互稱為共軛圖共軛圖。例如上圖的共軛圖是。例如上圖的共軛圖是: 它們分別表示的它們分別表示的10的分拆是的分拆是: = 4221; *=3222; . . . . . . . . . . 共軛圖共軛圖*圖圖 . . . . . . . . . . 的圖的圖16當(dāng)某個分拆當(dāng)某個分拆與它的共軛分拆與它的共軛分拆*完全相同時完全相同時: = *;或者說或者說的圖是一個對稱方陣時的圖是一個對稱方陣時,我我們把拆分們把拆分稱為稱為自共軛分拆自共軛分拆。例如：將例如：將12拆分成：拆分成：12= 4+4+2+2； = 4222; 其圖如下：其圖如下： 它的轉(zhuǎn)置與自身

12、一樣。它的轉(zhuǎn)置與自身一樣。 它關(guān)于主對角線對稱。它關(guān)于主對角線對稱。 . . . . . . . . . . . . 的圖的圖17 定理：定理：n的自共軛拆分的個數(shù)等于的自共軛拆分的個數(shù)等于n分成各類分成各類 都不相等且都是奇數(shù)的拆分的個數(shù)。都不相等且都是奇數(shù)的拆分的個數(shù)。 證明：設(shè)證明：設(shè) ,其中其中n1n2nk。顯見這是一個把顯見這是一個把n分成各類都不相同且都是奇分成各類都不相同且都是奇數(shù)的拆分，對應(yīng)的圖的第數(shù)的拆分，對應(yīng)的圖的第i行有行有2ni+1個方格。個方格。構(gòu)造一新的圖，使其第構(gòu)造一新的圖，使其第i行及第行及第i列都是列都是ni+1個個方格。注意到交叉處的方格重合，故方格。注意到

13、交叉處的方格重合，故:kiinn1)12(18 這恰用掉原圖的第這恰用掉原圖的第i行的行的2ni+1個方格。而新構(gòu)造個方格。而新構(gòu)造 的圖以對角線為軸線對稱，的圖以對角線為軸線對稱， 即對應(yīng)的拆分即對應(yīng)的拆分是自共軛的。是自共軛的。 反之，對任一自共軛拆分，用其圖中第反之，對任一自共軛拆分，用其圖中第i行行及第及第j列的全部方格（共列的全部方格（共2ni+1個）作為新構(gòu)造個）作為新構(gòu)造的圖的第的圖的第i行，這新得到的圖對應(yīng)的拆分又是行，這新得到的圖對應(yīng)的拆分又是n分成各類都不相等且都是奇數(shù)的拆分。以上討分成各類都不相等且都是奇數(shù)的拆分。以上討論建立了兩種拆分間的雙射函數(shù)。論建立了兩種拆分間的雙

14、射函數(shù)。19定理：定理：n分成各類互不相同的拆分的個數(shù)分成各類互不相同的拆分的個數(shù),等于等于n 分成各類都是奇數(shù)的拆分的個數(shù)。分成各類都是奇數(shù)的拆分的個數(shù)。 證明：設(shè)證明：設(shè) ,其中其中ni為奇數(shù)，為奇數(shù)，ri為為ni的重的重復(fù)次數(shù)。注意到復(fù)次數(shù)。注意到rt可表示為可表示為 10,20ktkkktbbbr 斷言斷言 n= b020n1+b121n1+b020n2+b121n2+ +b020ni+b121ni+b020nj+b121nj+ 0tiinrn20中取掉中取掉0項（項（bk=0），就構(gòu)成），就構(gòu)成n的各類互不相等的各類互不相等 的拆分。事實上的拆分。事實上:tjsitijsiknnbn

15、bnbji222212 若若s=t，顯見有，顯見有ninj；若；若st（不妨設(shè)（不妨設(shè)ts）, 但但ni=nj2t-s， 這導(dǎo)致這導(dǎo)致ni為偶數(shù)，與題設(shè)矛盾，故為偶數(shù)，與題設(shè)矛盾，故斷言為真。又上述構(gòu)造過程的逆也成立。斷言為真。又上述構(gòu)造過程的逆也成立。 這這就建立了兩種拆分間的雙射函數(shù)。就建立了兩種拆分間的雙射函數(shù)。 21 由于共軛分拆通過轉(zhuǎn)置得到，那么由于共軛分拆通過轉(zhuǎn)置得到，那么*的個的個 數(shù)就等于數(shù)就等于 的最大部分。的最大部分。例如：例如：10 = 5+3+1+1； = 513112；圖如下：；圖如下： . . . . . . . . . . 的圖的圖 . . . . . . . .

16、 . . *的圖的圖 10的最大部分是的最大部分是5；圖的第一行是圖的第一行是5；轉(zhuǎn)置后；轉(zhuǎn)置后*圖的第一列是五行，如同五個部分圖的第一列是五行，如同五個部分*= 41221222定理：定理：n分成分成k個類的拆分的個數(shù)，等于個類的拆分的個數(shù)，等于n分成以分成以 k為最大類的拆分的個數(shù)。為最大類的拆分的個數(shù)。例如，當(dāng)例如，當(dāng)n=6時，以時，以3作為最大類的拆分有作為最大類的拆分有3個個:3+1+1+1， 3+2+1， 3+3而分成而分成3個類的拆分也有個類的拆分也有3個：個： 4+1+1， 3+2+1， 2+2+2 23 證明：考慮一個拆分：證明：考慮一個拆分： 例如例如11=5+4+1+1，

17、并構(gòu)作一個相應(yīng)的圖，并構(gòu)作一個相應(yīng)的圖，在圖中每個類均表示成一行小點，每行的在圖中每個類均表示成一行小點，每行的點數(shù)等于類本身的數(shù)目，考慮到拆分組的點數(shù)等于類本身的數(shù)目，考慮到拆分組的分量由左向右成一遞減序列，故對應(yīng)的圖分量由左向右成一遞減序列，故對應(yīng)的圖從上而下，各行點數(shù)也自然呈遞減數(shù)列。從上而下，各行點數(shù)也自然呈遞減數(shù)列。 . . . . . . . . . . . 圖圖24分拆數(shù)序列分拆數(shù)序列pn的生成函數(shù)的生成函數(shù) 定理定理8.3.1 n的拆分數(shù)的拆分數(shù)Pn的生成函數(shù)是：的生成函數(shù)是： )1()1()(10101jjnnnPxxpxG設(shè)證明：事實上，當(dāng)證明：事實上，當(dāng)|x|1時，等式的

18、右邊的一般式：時，等式的右邊的一般式： .).1 (.)1 (.)1 (.)1 (1)1 (1)1 (1)1 (1633342222113322111xaxaxaxaxaxaxaxaxaxajjj25展開式的系數(shù)中，常數(shù)項是展開式的系數(shù)中，常數(shù)項是1；一次項只能有乘；一次項只能有乘積的第一個因子中得到，從第二項開始積的第一個因子中得到，從第二項開始x的次的次數(shù)已經(jīng)大于數(shù)已經(jīng)大于2了；了；.；xn在的項，在的項， 由第一個因子選擇由第一個因子選擇 ,第二個因子選擇第二個因子選擇 等等確定；等等確定； xn項的冪有關(guān)系：項的冪有關(guān)系：nkjkjjkjjjjjjjjjxaaaxaxaxaxaxak)

19、(1)()()1 (1212110022011111xa222xa26最后，取最后，取a1=a2=1，即得公式：，即得公式： kkkk.2.221.1121 xn項的系數(shù)中的第一項項的系數(shù)中的第一項 確定確定n的一個拆分，即：的一個拆分，即：kkaaa2121nk.321)1()1()(10101jjnnnPxxpxG設(shè)27 定理定理8.3.2: n拆分拆分k類類的分拆數(shù)的分拆數(shù)Pnk的生成函數(shù)是的生成函數(shù)是: 該定理的證明與定理該定理的證明與定理8.3.1一樣，同學(xué)們可以一樣，同學(xué)們可以自己證明。自己證明。 定理定理8.3.3: n拆分成僅有奇數(shù)類拆分成僅有奇數(shù)類的分拆數(shù)的分拆數(shù)Pn的的生成

20、函數(shù)是生成函數(shù)是:112102)1 ()1 ()1 ()(kknnknxxxxxpxG)1)(1)(1 ()1 ()1 ()1 ()(1056321513103xxxxxxxxxxpxGnnn28定理定理8.3.4：n分成分成各類互不相等各類互不相等的拆分數(shù)的拆分數(shù)Pn的生的生 成函數(shù)是：成函數(shù)是：定理定理8.3.5：n分成分成各類互不相等的奇數(shù)類各類互不相等的奇數(shù)類的拆分的拆分 數(shù)數(shù)Pn的生成函數(shù)是：的生成函數(shù)是：實際上實際上G3(x) = G4(x) ,下面我們給于證明。下面我們給于證明。)1)(1)(1 ()(3204xxxxpxGnnn0125)1()(kkxxG29 證明：事實上我們

21、將證明：事實上我們將G3(x) 變形就得到變形就得到G4(x) ：)()1 ()1)(1)(1 ()1)(1)(1)(1)(1)(1 ()1 ()1 ()1 ()1 (1)()1 ()1 ()1 ()(4132332201212120123151313xGxxxxxxxxxxxxxxxGxxxxGjjjjjjjjjj30例例 1 有有1、2、3、4克的砝碼各一枚，問能稱出克的砝碼各一枚，問能稱出 哪幾種重量？哪幾種重量？ 對能稱出的重量有幾種可稱對能稱出的重量有幾種可稱量方案？量方案？解：解： 1098765432414222221)1 ()(xxxxxxxxxxxxGi 從從G(x)展開式中

22、展開式中x的冪次知，可稱出的冪次知，可稱出110克的重量，系數(shù)即為對應(yīng)的稱量方案數(shù)。如對克的重量，系數(shù)即為對應(yīng)的稱量方案數(shù)。如對2x5項，即稱量項，即稱量5克的方案有兩種：克的方案有兩種：31 5 = 3+2 = 4+1 同樣，同樣， 有有 6=1+2+3=4+2， 10=1+2+3+4 故稱出故稱出6克的方案數(shù)有兩種，克的方案數(shù)有兩種， 稱出稱出10克的方克的方案數(shù)是唯一的。案數(shù)是唯一的。例例2 求用求用1角，角，2角，角，3角的郵票貼出不同數(shù)值的角的郵票貼出不同數(shù)值的方案數(shù)。方案數(shù)。 解：因郵票允許重復(fù)，故生成函數(shù)為：解：因郵票允許重復(fù)，故生成函數(shù)為：32 以以x4為例，其系數(shù)為為例，其系

23、數(shù)為4，即，即4拆分成拆分成1、2、3之之和的拆分數(shù)為和的拆分數(shù)為4，拆分方案為：，拆分方案為：4=1+1+1+1， 4=1+1+2， 4=2+2， 4=1+3 njjjjjjnxxxxxxxxxxxxxxxG4321312113121030204321)1 ()1 ()1 (1)1 ()1 ()1 ()(33例例 3 若有若有1克的砝碼克的砝碼3枚枚,2克的砝碼克的砝碼4枚枚,4克的克的 砝碼砝碼2枚。問能稱出哪些重量？有幾種方案？枚。問能稱出哪些重量？有幾種方案？解：解： G(x)=(1+x+x2+x3)(1+x2+x4+x6+x8)(1+x4+x8) =(1+x+x2+2x3+2x4+2

24、x5+2x6+2x7+2x8+2x9+x10 +x11) (1+x4+x8)=1+x+2x2+2x3+3x4+3x5+4x6+4x7+5x8+5x9+5x10+5x11+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19 觀察展開式各項中觀察展開式各項中x的冪次及其系數(shù)即知答案。的冪次及其系數(shù)即知答案。34例例 4 整數(shù)整數(shù)n拆分成拆分成1，2，3，, m的和，并允許的和，并允許 重復(fù)，求其生成函數(shù)。若其中重復(fù)，求其生成函數(shù)。若其中m至少出現(xiàn)至少出現(xiàn)一次，其生成函數(shù)如何？一次，其生成函數(shù)如何？解：當(dāng)解：當(dāng)n允許重復(fù)地拆分成允許重復(fù)地拆分成1，2，m的和時，的和時，其生成

25、函數(shù)：其生成函數(shù)：mjmjjjjjxxxxxxxG111111)(20020135 若拆分中若拆分中m至少出現(xiàn)一次，其生成函數(shù)：至少出現(xiàn)一次，其生成函數(shù)：00202)(jmjjjjjxxxxG顯見顯見 G2(x)=G1(x)(1-xm)G1(x)= xmG1(x) 其組合意義是：其組合意義是：n拆分成拆分成1, 2, , m的和的的和的拆分數(shù)，拆分數(shù)， 減去減去n拆分成拆分成1, 2, , m-1的和的拆分的和的拆分數(shù)，數(shù)， 即為至少出現(xiàn)一個即為至少出現(xiàn)一個m的拆分數(shù)。的拆分數(shù)。36例例 5 設(shè)有設(shè)有1、 2、 4、 8、 16、32克砝碼各一枚，克砝碼各一枚， 問能稱出哪些重量？問能稱出哪些重量？ 分別有幾種方案？分別有幾種方案？解：解： 由生成函數(shù)知，用給定的砝碼能稱出從由生成函數(shù)知，用給定的砝碼能稱出從1克到克到63克的各種重量，且其方案都是唯一的。克的各種重量，且其方案都是唯一的。630643264163281648242321684211111111111111)1)(1)(1)(1)(1)(1 ()(kkxxxxxxxxxxxxxxxxxxxxxxG37有有 序序 拆拆 分分 以上討論的關(guān)于整數(shù)以上討論的關(guān)于整數(shù)n的拆分都是無序拆分。的拆分都是無序拆分。即在定義中強加了一種序即在定義中強加了一種序a1a2am1?；??；蚩梢暼缈?/p>