1、組合數(shù)學,1,整數(shù)的拆分,本講內(nèi)容 1. 整數(shù)拆分的概念和計算 2. Ferrers圖 目的要求 理解整數(shù)拆分的概念 會用生成函數(shù)和有關(guān)公式求正整數(shù)的拆分數(shù) 了解Ferrers圖,組合數(shù)學,2,1. 整數(shù)的拆分,第1章介紹了： (1) 將n個不同的球放入k個不同的盒子多重排列 (2) 將n個相同的球放入k個不同的盒子多重組合 還存在這樣一類問題：將n個相同的球放入k個相同的盒子，每個盒子至少放1個。 這類問題等價于如下問題：對于方程n1n2nkn，求滿足條件n1n2nk1的正整數(shù)解的個數(shù)。,組合數(shù)學,3,1. 整數(shù)的拆分,定義2.6.1 設(shè)n為正整數(shù)，有k個正整數(shù)n1，n2，nk滿足： （1）

2、nn1n2nk； （2）n1n2nk1 ； 則稱n1,n2,nk為正整數(shù)n的一個k拆分，其中ni (1ik)稱為該k拆分的分量。n的k拆分的個數(shù)稱為n的k拆分數(shù)。n的所有拆分（k取遍所有可能的值）的個數(shù)稱為n的拆分數(shù)。,組合數(shù)學,4,1. 整數(shù)的拆分,正整數(shù)的拆分的模型是：n個相同的球放入k個相同的盒子，每個盒子至少放1個。 為了方便敘述，本書采用以下記號：pk(n)表示正整數(shù)n的k拆分數(shù)，p(n)表示正整數(shù)n的所有拆分數(shù)。 當kn時，正整數(shù)n的k拆分不存在。為了以后計算的方便，規(guī)定這時的拆分數(shù)為0，即當kn時，pk(n) =0。,組合數(shù)學,5,1. 整數(shù)的拆分,正整數(shù)5的所有拆分如下： (1

3、) 5=5 (2) 5=41 (3) 5=32 (4) 5=311 (5) 5=221 (6) 5=2111 (7) 5=11111,組合數(shù)學,6,1. 整數(shù)的拆分,所以， p1(5)=1（5=5） p2(5)=2（5=41，5=32） p3(5)=2（5=311，5=221） p4(5)=1（5=2111） p5(5)=1（5=11111） p(5)=7 3和1都是5的3拆分5=311的分量。,組合數(shù)學,7,1. 整數(shù)的拆分,人們希望對于給定的n，不需要列出所有拆分，而是有某種方法直接計算出pk(n)和p(n)。生成函數(shù)就可以用來求正整數(shù)的拆分數(shù)。 例3-6 有足夠多面值分別為1元、2元、3

4、元、4元和5元的郵票，問有多少種方案貼出5元的郵資？,組合數(shù)學,8,1. 整數(shù)的拆分,解 利用生成函數(shù)，有（為了節(jié)省篇幅，省略了指數(shù)大于5的項） G(x)(1xx2x3x4x5) (1x2x4)(1x3) (1x4)(1x5) (1x2x22x33x43x5) (1x3)(1x4) (1x5),組合數(shù)學,9,1. 整數(shù)的拆分,續(xù)解(1x2x23x34x45x5) (1x4)(1x5) (1x2x23x35x46x5) (1x5) 1x2x23x35x47x5 由于x5的系數(shù)是7，這表明有7種方案貼出5元的郵資。這恰與實例3-4的p(5) =7吻合。 p(0)=1, p(1)=1, p(2)=2

5、, p(3)=3, p(4)=5,組合數(shù)學,10,1. 整數(shù)的拆分,例3-7 有1元郵票3枚，2元郵票2枚和4元郵票1枚，問有多少種方案貼出5元的郵資？ 解 利用生成函數(shù)，有 G(x)(1xx2x3)(1x2x4)(1x4) (1x2x22x32x42x5x6x7) (1x4) 1x2x22x33x43x53x6 3x72x82x9x10 x11,組合數(shù)學,11,1. 整數(shù)的拆分,由于x5的系數(shù)是3，這表明有3種方案貼出5元的郵資。實際上，這3種方案是：41，221，2111。 從例3-7的解答中可以看出：由1元郵票3枚，2元郵票2枚和4元郵票1枚可以貼出不超過11元的各個整數(shù)元的郵資，超過1

6、1元的郵資無法貼出。,組合數(shù)學,12,1. 整數(shù)的拆分,定理3-2 關(guān)于正整數(shù)n的k拆分數(shù)pk(n)，有： （1）p1(n) =1(3-10) （2）pn(n) =1(3-11) （3）pn1(n) =1 (3-12) （4）(3-13) （5）(3-14),其中， 表示不大于n的最大整數(shù)。,組合數(shù)學,13,1. 整數(shù)的拆分,例3-8 求7的3拆分數(shù)p3(7)。 解利用公式(3-14)、(3-10)、(3-12)和(3-13)，有 p3(7)= p1(73)p2(73)p3(73) = p1(4)p2(4)p3(4),組合數(shù)學,14,1. 整數(shù)的拆分,例3-9 求10的4拆分數(shù)p4(10)。

7、解 利用多個計算拆分數(shù)的公式，有 P4(10)= p1(6)p2(6)p3(6)p4(6) =13p3(6)p1(2)p2(2),組合數(shù)學,15,2. Ferrers圖,Ferrers圖是研究拆分的一種有效工具。 設(shè)正整數(shù)n的一個k拆分為nn1n2nk（n1n2nk1）?？梢杂靡粋€含有n個點的點陣圖表示這個拆分：圖的第1行有n1個點，第2行有n2個點，第k行有nk個點；并且每一行最左邊的點上下對齊。這樣的圖稱為正整數(shù)n的一個k拆分的Ferrers圖。,組合數(shù)學,16,2. Ferrers圖,例如，正整數(shù)10的4拆分10=5221的Ferrers圖如下圖所示。 顯然，n的拆分與其Ferrers圖

8、之間是一一對應(yīng)關(guān)系。,組合數(shù)學,17,2. Ferrers圖,把一個Ferrers圖的行與列互換，且保持相對位置不變，就得到又一個Ferrers圖，稱為原Ferrers圖的共軛圖。共軛Ferrers圖對應(yīng)的拆分稱為原Ferrers圖的共軛拆分。如果正整數(shù)n的一個拆分與其共軛拆分相同，則稱該拆分為自共軛拆分。,組合數(shù)學,18,2. Ferrers圖,例如，下右圖是下左圖的共軛圖，它對應(yīng)正整數(shù)10的5拆分10=43111 正整數(shù)10的5拆分10=43111是正整數(shù)10的4拆分10=5221的共軛拆分。而10=52111是自共軛拆分。,組合數(shù)學,19,2. Ferrers圖,定理3.3 正整數(shù)n的k

9、拆分的個數(shù)等于n的最大分量為k的拆分數(shù)。 證明 n的每一個k拆分對應(yīng)一個有且僅有k行點陣的Ferrers圖；而該Ferrers圖的共軛Ferrers圖的第一行必定是有且僅有k個點。 因此，n的k拆分與最大分量為k的共軛拆分一一對應(yīng)。至此，定理得證。,組合數(shù)學,20,2. Ferrers圖,例3-11 根據(jù)定理3.3，利用生成函數(shù)重解例3-8。 解 根據(jù)定理3-3，7的3拆分的個數(shù)等于7的最大分量為3的拆分數(shù)。而7的最大分量為3的拆分數(shù)的生成函數(shù)為（為了節(jié)省篇幅，省略了最終導致指數(shù)大于7的項） G(x)(1xx2x3x4) (1x2x4)(x3x6),組合數(shù)學,21,2. Ferrers圖,續(xù)解 x3(1xx2x3x4) (1x2x4)(1x3) x3(1x2x22x33x4) (1x3) x3x42x53x64x7 由于x7的系數(shù)是4，這表明7的最大分量為3的拆分數(shù)是4