11.整数的拆分

1、组合数学,1,整数的拆分,本讲内容 1. 整数拆分的概念和计算 2. Ferrers图 目的要求 理解整数拆分的概念 会用生成函数和有关公式求正整数的拆分数 了解Ferrers图,组合数学,2,1. 整数的拆分,第1章介绍了： (1) 将n个不同的球放入k个不同的盒子多重排列 (2) 将n个相同的球放入k个不同的盒子多重组合 还存在这样一类问题：将n个相同的球放入k个相同的盒子，每个盒子至少放1个。 这类问题等价于如下问题：对于方程n1n2nkn，求满足条件n1n2nk1的正整数解的个数。,组合数学,3,1. 整数的拆分,定义2.6.1 设n为正整数，有k个正整数n1，n2，nk满足： （1）

2、nn1n2nk； （2）n1n2nk1 ； 则称n1,n2,nk为正整数n的一个k拆分，其中ni (1ik)称为该k拆分的分量。n的k拆分的个数称为n的k拆分数。n的所有拆分（k取遍所有可能的值）的个数称为n的拆分数。,组合数学,4,1. 整数的拆分,正整数的拆分的模型是：n个相同的球放入k个相同的盒子，每个盒子至少放1个。 为了方便叙述，本书采用以下记号：pk(n)表示正整数n的k拆分数，p(n)表示正整数n的所有拆分数。 当kn时，正整数n的k拆分不存在。为了以后计算的方便，规定这时的拆分数为0，即当kn时，pk(n) =0。,组合数学,5,1. 整数的拆分,正整数5的所有拆分如下： (1

3、) 5=5 (2) 5=41 (3) 5=32 (4) 5=311 (5) 5=221 (6) 5=2111 (7) 5=11111,组合数学,6,1. 整数的拆分,所以， 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的分量。,组合数学,7,1. 整数的拆分,人们希望对于给定的n，不需要列出所有拆分，而是有某种方法直接计算出pk(n)和p(n)。生成函数就可以用来求正整数的拆分数。 例3-6 有足够多面值分别为1元、2元、3

4、元、4元和5元的邮票，问有多少种方案贴出5元的邮资？,组合数学,8,1. 整数的拆分,解 利用生成函数，有（为了节省篇幅，省略了指数大于5的项） G(x)(1xx2x3x4x5) (1x2x4)(1x3) (1x4)(1x5) (1x2x22x33x43x5) (1x3)(1x4) (1x5),组合数学,9,1. 整数的拆分,续解(1x2x23x34x45x5) (1x4)(1x5) (1x2x23x35x46x5) (1x5) 1x2x23x35x47x5 由于x5的系数是7，这表明有7种方案贴出5元的邮资。这恰与实例3-4的p(5) =7吻合。 p(0)=1, p(1)=1, p(2)=2

5、, p(3)=3, p(4)=5,组合数学,10,1. 整数的拆分,例3-7 有1元邮票3枚，2元邮票2枚和4元邮票1枚，问有多少种方案贴出5元的邮资？ 解 利用生成函数，有 G(x)(1xx2x3)(1x2x4)(1x4) (1x2x22x32x42x5x6x7) (1x4) 1x2x22x33x43x53x6 3x72x82x9x10 x11,组合数学,11,1. 整数的拆分,由于x5的系数是3，这表明有3种方案贴出5元的邮资。实际上，这3种方案是：41，221，2111。 从例3-7的解答中可以看出：由1元邮票3枚，2元邮票2枚和4元邮票1枚可以贴出不超过11元的各个整数元的邮资，超过1

6、1元的邮资无法贴出。,组合数学,12,1. 整数的拆分,定理3-2 关于正整数n的k拆分数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的最大整数。,组合数学,13,1. 整数的拆分,例3-8 求7的3拆分数p3(7)。 解利用公式(3-14)、(3-10)、(3-12)和(3-13)，有 p3(7)= p1(73)p2(73)p3(73) = p1(4)p2(4)p3(4),组合数学,14,1. 整数的拆分,例3-9 求10的4拆分数p4(10)。

7、解 利用多个计算拆分数的公式，有 P4(10)= p1(6)p2(6)p3(6)p4(6) =13p3(6)p1(2)p2(2),组合数学,15,2. Ferrers图,Ferrers图是研究拆分的一种有效工具。 设正整数n的一个k拆分为nn1n2nk（n1n2nk1）。可以用一个含有n个点的点阵图表示这个拆分：图的第1行有n1个点，第2行有n2个点，第k行有nk个点；并且每一行最左边的点上下对齐。这样的图称为正整数n的一个k拆分的Ferrers图。,组合数学,16,2. Ferrers图,例如，正整数10的4拆分10=5221的Ferrers图如下图所示。 显然，n的拆分与其Ferrers图

8、之间是一一对应关系。,组合数学,17,2. Ferrers图,把一个Ferrers图的行与列互换，且保持相对位置不变，就得到又一个Ferrers图，称为原Ferrers图的共轭图。共轭Ferrers图对应的拆分称为原Ferrers图的共轭拆分。如果正整数n的一个拆分与其共轭拆分相同，则称该拆分为自共轭拆分。,组合数学,18,2. Ferrers图,例如，下右图是下左图的共轭图，它对应正整数10的5拆分10=43111 正整数10的5拆分10=43111是正整数10的4拆分10=5221的共轭拆分。而10=52111是自共轭拆分。,组合数学,19,2. Ferrers图,定理3.3 正整数n的k

9、拆分的个数等于n的最大分量为k的拆分数。 证明 n的每一个k拆分对应一个有且仅有k行点阵的Ferrers图；而该Ferrers图的共轭Ferrers图的第一行必定是有且仅有k个点。 因此，n的k拆分与最大分量为k的共轭拆分一一对应。至此，定理得证。,组合数学,20,2. Ferrers图,例3-11 根据定理3.3，利用生成函数重解例3-8。 解 根据定理3-3，7的3拆分的个数等于7的最大分量为3的拆分数。而7的最大分量为3的拆分数的生成函数为（为了节省篇幅，省略了最终导致指数大于7的项） G(x)(1xx2x3x4) (1x2x4)(x3x6),组合数学,21,2. Ferrers图,续解 x3(1xx2x3x4) (1x2x4)(1x3) x3(1x2x22x33x4) (1x3) x3x42x53x64x7 由于x7的系数是4，这表明7的最大分量为3的拆分数是4