組合數學(24)

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

2、在正整數的集合 n1, n2, nk (其中其中1 k n，ni n)使得使得 n1 n2nkn則稱則稱 n1, n2, nk 是是n的一個的一個分拆分拆。分拆個數可以記為。分拆個數可以記為Pnk 如果如果n的一個分拆含有的一個分拆含有an個個n, an-1個個(n-1),a2個個2和和a1個個1。即。即: nnan + (n-1)an-1 + + 2a2 + 1a13則將該分拆則將該分拆 記作記作: 上述表示方法僅僅是個記號上述表示方法僅僅是個記號, 沒有指數運沒有指數運算的意義。算的意義。例如：例如：整數整數n 拆分方式拆分方式 拆分個數拆分個數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取取整數整數4來更換表示形式：它可以是來更換表示形式：它可以是1個個4；一一個個3和一個和一個1；兩個兩個2；一個；一個2和兩個和兩個1；四個四個1。這樣，整數這樣，整數4的的分拆個數：分拆個數： Pn1=P43=P44=1 ； P42= 2共計為共計為5 ； 同時同時4的分拆可以記為：的分拆可以記為： 41, 3111, 22, 2112, 14注意注意pn與與Pnk是兩個不同概念的分拆數，是兩個不同概念的分拆數， pn表示表示正整數正整數n的分拆數，沒

4、有限制分拆的分拆數，沒有限制分拆n后各類的后各類的數量；數量； Pnk表示分拆表示分拆n后各類的數量必須是后各類的數量必須是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 根據根據k值來分：值來分： k=1,2,3,.5;故分別有：故分別有： Pn1=1; Pn2=2; Pn3=2; Pn4=1; Pn5=1;令令pn表示正整數表示正整數n的總分拆數，為了方便起見，的總分拆數，為了方便起見， 把初值：把初值： p0 = 1 ，分拆數構成的序列為：，分拆數

5、構成的序列為： p0, p1, p2, p3, pn,. 6由前面的討論我們已經有：由前面的討論我們已經有： p0 = 1, p1 = 1, p2 = 2, p3 = 3, p4 = 5, 對上述序列我們討論遞推關系。對上述序列我們討論遞推關系。定理：定理：n分拆數分拆數Pnk滿足下列遞推關系：滿足下列遞推關系：證明：證明：只證第一式，第二式表示將只證第一式，第二式表示將n分拆成分拆成1個個部分和部分和n個部分，顯然只有一種可能個部分，顯然只有一種可能。設設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 可見可見, 為一雙射函數。因此：為一雙射函數。因此： 注意到注意到 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 定義數組定義數組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結束。結束。12觀察公式：觀察公式： pn等價于方程等價于方程:nan+(n-1)an-1+.+2a2+1a1=n的非負整數解的非負整數解 an,an-1,.,a2,a1的個數。的個數。令令為為n的分拆：的分拆： 及及 a1a2a3ak1 12112.) 1(aaaannnnknnan1例如：例如：10=10=9+1=8+2=8+1+1=7+3=7+2+1=

9、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 由上面的例子看出，可以對分拆著兩類化分：由上面的例子看出，可以對分拆著兩類化分： 第一類型：以分拆成的各類數量為拆分標第一類型：以分拆成的各類數量為拆分標準；準； 第二類型：以分拆成的各類中最大的數為第二類型：以分拆成的各類中最大的數為拆分標準；拆分標準； 顯然，拆分類中最大類的數越大，該類的數顯然，拆分類中最大類的數越大，該類的數量就越少：將量就越少：將10分拆為分拆為9+1只有兩類，而：只有兩類，而： 10=2+1+1+1+1+1+1+1+1就有就有9類。類。14 我們把我們

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

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

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

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

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

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

16、 . *的圖的圖 10的最大部分是的最大部分是5；圖的第一行是圖的第一行是5；轉置后；轉置后*圖的第一列是五行，如同五個部分圖的第一列是五行，如同五個部分*= 41221222定理：定理：n分成分成k個類的拆分的個數，等于個類的拆分的個數，等于n分成以分成以 k為最大類的拆分的個數。為最大類的拆分的個數。例如，當例如，當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、作一個相應的圖，并構作一個相應的圖，在圖中每個類均表示成一行小點，每行的在圖中每個類均表示成一行小點，每行的點數等于類本身的數目，考慮到拆分組的點數等于類本身的數目，考慮到拆分組的分量由左向右成一遞減序列，故對應的圖分量由左向右成一遞減序列，故對應的圖從上而下，各行點數也自然呈遞減數列。從上而下，各行點數也自然呈遞減數列。 . . . . . . . . . . . 圖圖24分拆數序列分拆數序列pn的生成函數的生成函數 定理定理8.3.1 n的拆分數的拆分數Pn的生成函數是：的生成函數是： )1()1()(10101jjnnnPxxpxG設證明：證明：事實上，當事實上，當|x|1時，等式的右邊

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

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

20、是生成函數是:112102)1 ()1 ()1 ()(kknnknxxxxxpxG)1)(1)(1 ()1 ()1 ()1 ()(1056321513103xxxxxxxxxxpxGnnn28定理定理8.3.4：n分成分成各類互不相等各類互不相等的拆分數的拆分數Pn的生的生 成函數是：成函數是：定理定理8.3.5：n分成分成各類互不相等的奇數類各類互不相等的奇數類的拆分的拆分 數數Pn的生成函數是：的生成函數是：實際上實際上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克的重量，系數即為對應的稱量方案數。如對克的重量，系數即為對應的稱量方案數。如對2x5項，即稱量項，即稱量5克的方案有兩種：克的方案有兩種：31 5 = 3+2 = 4+1 同樣，同樣， 有有 6=1+2+3=4+2， 10=1+2+3+4 故稱出故稱出6克的方案數有兩種，克的方案數有兩種， 稱出稱出10克的方克的方案數是唯一的。案數是唯一的。例例2 求用求用1角，角，2角，角，3角的郵票貼出不同數值的角的郵票貼出不同數值的方案數。方案數。 解：因郵票允許重復，故生成函數為：解：因郵票允許重復，故生成函數為：32 以以x4為例，其系數為為例，其系數為

23、4，即，即4拆分成拆分成1、2、3之之和的拆分數為和的拆分數為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+2x5

24、+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的冪次及其系數即知答案。的冪次及其系數即知答案。34例例 4 整數整數n拆分成拆分成1，2，3，, m的和，并允許的和，并允許 重復，求其生成函數。若其中重復，求其生成函數。若其中m至少出現至少出現一次，其生成函數如何？一次，其生成函數如何？解：當解：當n允許重復地拆分成允許重復地拆分成1，2，m的和時，的和時，其生成函數

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