组合数学课件-第二章第四节整数的拆分.ppt

1、1第第2章章 递推关系与母函数递推关系与母函数 2.1 2.1 递推关系递推关系 2.2 2.2 母函数母函数(生成函数生成函数)2.3 Fibonacci 2.3 Fibonacci数列数列 2.4 2.4 优选法与优选法与FibonacciFibonacci序列的应用序列的应用 2.5 2.5 母函数的性质母函数的性质 2.6 2.6 线性常系数齐次递推关系线性常系数齐次递推关系 2.7 2.7 关于常系数非齐次递推关系关于常系数非齐次递推关系 2.8 2.8 整数的拆分整数的拆分 2.9 ferrers2.9 ferrers图像图像 2.10 2.10 拆分数估计拆分数估计 2.11 2

2、.11 指数型母函数指数型母函数 2.12 2.12 广义二项式定理广义二项式定理 2.13 2.13 应用举例应用举例 2.14 2.14 非线性递推关系举例非线性递推关系举例 2.15 2.15 递推关系解法的补充递推关系解法的补充22.8：整数的拆分：整数的拆分 1 1、拆分的概念、拆分的概念 2 2、拆分的模型、拆分的模型 3 3、拆分算法、拆分算法:递归实现递归实现 4 4、用母函数讨论拆分数、用母函数讨论拆分数32.8：整数的拆分：整数的拆分 所谓整数的拆分，是指把一个正整所谓整数的拆分，是指把一个正整数拆分成若干正整数的和。不同的拆分数拆分成若干正整数的和。不同的拆分法的数目称为

3、拆分数法的数目称为拆分数例如：考虑正整数例如：考虑正整数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 通常用通常用p(np(n)表示整数表示整数n n拆分成若干拆分成若干正整数的和的拆分数，也可说成方案正整数的和的拆分数，也可说成方案数数 例如例如p(4)=5p(4)=5。1 1、拆分的概念拆分的概念4(1)(1)、C(n,rC(n,r)2 2、拆分的模型拆分的模型2.8：整数的拆分：整数的拆分 从从n n个不同的球中取出个不同的球中取出r r个个,放进放进r r个相同的个相同的盒子中盒子

4、中,不许空盒不许空盒,有多少种放法有多少种放法.(2)(2)、P(n,rP(n,r)从从n n个不同的球中取出个不同的球中取出r r个个,放进放进r r个不相同个不相同的盒子中的盒子中,不许空盒不许空盒,有多少种放法有多少种放法.5(3)(3)、从、从n n个不同元素中取个不同元素中取r r个允许重复的组合个允许重复的组合2.8：整数的拆分：整数的拆分 r r个相同的球放进个相同的球放进n n个不同的盒子中个不同的盒子中,允许允许空盒空盒,有多少种放法有多少种放法.以正整数以正整数4 4为例：为例：4=44=4，4=3+14=3+1，4=2+24=2+2，4=2+1+14=2+1+1，4=1+

5、1+1+14=1+1+1+1(4)(4)、正整数、正整数n n的拆分数的拆分数6 正整数正整数n n的拆分，相当于把的拆分，相当于把n n个无区别个无区别的球放进的球放进n n个无区别的盒子，盒子中允许放个无区别的盒子，盒子中允许放一个以上的球，也允许空着一个以上的球，也允许空着 以正整数以正整数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 2.8：整数的拆分：整数的拆分*7 3 3、拆分算法、拆分算法:递归实现递归实现 定义一个函数定义一个函数Q(n,mQ(n,m)：

6、表示整数：表示整数n n的所有加的所有加数都不超过数都不超过m m的拆分数。的拆分数。n n的拆分数就可以表示为的拆分数就可以表示为Q(n,nQ(n,n)Q(n,nQ(n,n)有以下递归关系有以下递归关系(1)Q(n,n)=1+Q(n,n-1)(1)Q(n,n)=1+Q(n,n-1)停止条件：停止条件：(1)Q(n,1)=1(1)Q(n,1)=1(2)Q(1,m)=1(2)Q(1,m)=12.8：整数的拆分：整数的拆分Q(n,mQ(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)8 int div

7、integer(int n,intint divinteger(int n,int m)m)if(n1|m1)if(n1|m1)printf(“error printf(“error”);”);elseelse if(n if(n=1|m=1)=1|m=1)return(1);return(1);elseelse if(n if(nm)m)return divinteger(n,n return divinteger(n,n)elseelse if(n if(n=m)=m)return(1+divinter(n,n-1);return(1+divinter(n,n-1);elseelse re

8、turn(divinteger(n,m-1)+divinteger(n-m,m);return(divinteger(n,m-1)+divinteger(n-m,m);2.8：整数的拆分：整数的拆分9 例例1 1 求求4 4的拆分数。的拆分数。解：分析下面的多项式解：分析下面的多项式x x4 4项的系数项的系数与与4 4的拆分数的关系的拆分数的关系.(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、用母函数讨论拆分数、用母函数讨论拆分数2.8：整数的拆分：整数的拆分4=1+1+1+1,

9、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，10 n n的拆分数的母函数。的拆分数的母函数。4 4、用母函数讨论拆分数、用母函数讨论拆分数.12xx.142xx.163xx.nxxxx11.111111322.8：整数的拆分：整数的拆分11 例例2 2 求求1 1角、角、2 2角、角、3 3角的邮票可贴角的邮票可贴出不同数值邮资的方案数的母函数。出不同数值邮资的方案数的母函数。解：解：单独用单独用1 1角的母函数为角的母函数为1+x+x1+x+x2 2+x+x3 3+单独用单独用2 2角邮票的母函数为角邮票的母函数为1+x1+x2

10、 2+x+x4 4+x+x6 6+单独用单独用3 3角邮票的母函数为角邮票的母函数为1+x1+x3 3+x+x6 6+x+x9 9+2.8：整数的拆分：整数的拆分12.)1.)(1.)(1()(63422xxxxxxxG)1)(1)(1(132xxx.543215432xxxxx2.8：整数的拆分：整数的拆分13 例例3 3 求正整数求正整数n n拆分成拆分成1,2,1,2,m m的和，的和，并允许重复的拆分数。如若其中并允许重复的拆分数。如若其中m m至少出现至少出现一次，试求它的方案数及其母函数。一次，试求它的方案数及其母函数。解解1 1：)1).(1)(1(12mxxx展开式中展开式中x

11、n项的系数就是要求的拆分数。项的系数就是要求的拆分数。2.8：整数的拆分：整数的拆分14 解解2 2：如果：如果m m至少出现一次。至少出现一次。)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：整数的拆分：整数的拆分152.8：整数的拆分：整数的拆分 正整数正整数n n拆分成拆分成1,2,1,2,m m的和，并允许的和，并允许重复的拆分数。重复的拆分数。若其中若其中m m至少出现一次，它的方案数等至少出现一次，它的方案数等于拆分

12、成于拆分成1,2,1,2,m,m的拆分数减去拆分成的拆分数减去拆分成1,2,1,2,m-1,m-1的拆分数。的拆分数。以正整数以正整数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+116 定理定理2.8.1 2.8.1 正整数正整数r r拆分成不同正整数和的拆拆分成不同正整数和的拆分数，等于拆分成奇正整数的拆分数？分数，等于拆分成奇正整数的拆分数？对比对比7 7拆分成不同正整数之和的拆分数和拆分成不同正整数之和的拆分数和拆分成奇数和的拆分数。拆分成奇数和的拆分数。解：解：7 7拆分成不同正整数和的所有

13、形式如下：拆分成不同正整数和的所有形式如下：7，6+1，5+2，4+3，4+2+1共共5种种 解：解：7 7拆分成奇数和的所有形式如下：拆分成奇数和的所有形式如下：7，5+1+1，3+3+1，3+1+1+1+1，1+1+1+1+1+1+1也是也是5种种2.8：整数的拆分：整数的拆分17 解：首先构造解：首先构造r r拆分成不同正整数和的拆分成不同正整数和的拆分序列的母函数：拆分序列的母函数：G(x)=(1+x)(1+x2)(1+x3)(1+x4)xx112).1)(1)(1(153xxx.).1.)(1(632xxxx.11.24xx.11.114836xxxx2.8：整数的拆分：整数的拆分1

14、8 定理定理2.8.2 n2.8.2 n拆分成其它数之和但重拆分成其它数之和但重复数不超过复数不超过2 2。其拆分数等于它拆分成不。其拆分数等于它拆分成不被被3 3除尽的数的和的拆分数。除尽的数的和的拆分数。考虑考虑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+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+

15、11+1+1+1+12.8：整数的拆分：整数的拆分19 解：解：n n拆分成重复数不超过拆分成重复数不超过2 2的数之和的拆分数，的数之和的拆分数，其母函数为：其母函数为：.11.11.11.11)(41239263xxxxxxxxxG).1)(1)(1(142xxx)1)(1()1(23xxxxG(x)=(1+x+x2)(1+x2+x4)(1+x3+x6)(1+x4+x8)2.8：整数的拆分：整数的拆分20 例例2-252-25 n n个完全相同的球放到个完全相同的球放到m m个无区个无区别别的盒子，不允许空盒，问共有多少种不的盒子，不允许空盒，问共有多少种不同的方案？其中同的方案？其中mn

16、mn。解：从解：从n n中取中取m m个球一个盒子放一个。个球一个盒子放一个。整数整数n-mn-m用不超过用不超过m m的数来拆分的拆分的数来拆分的拆分数。数。)1).(1)(1(12mxxx展开中展开中x xn-mn-m项的系数项的系数2.8：整数的拆分：整数的拆分21 例例6 n6 n个完全相同的球放到个完全相同的球放到m m个有区别个有区别的盒子，的盒子，允许空盒，问共有多少种不同的允许空盒，问共有多少种不同的方案？其中方案？其中mnmn。解：第一盒，用解：第一盒，用1 1代表不放球，用代表不放球，用x x代表代表放一个球，用放一个球，用x2代表放两个球，代表放两个球，。单独第。单独第一

17、盒的母函数可构造为：一盒的母函数可构造为：1+1+x+x2+xn+其它盒也有同样的情况，共其它盒也有同样的情况，共m m个盒子。个盒子。盒第第二盒第一盒m .)1.).(1.)(1()(222xxxxxxxG2.8：整数的拆分：整数的拆分22 例例7 n7 n个完全相同的球放到个完全相同的球放到m m个有区别个有区别的盒子，的盒子，不允许空盒，问共有多少种不同不允许空盒，问共有多少种不同的方案？其中的方案？其中mnmn。解：第一盒，用解：第一盒，用1 1代表不放球，用代表不放球，用x x代代表放一个球，用表放一个球，用x2代表放两个球，代表放两个球，。因。因为不允许空盒，因此常数项为零，单独第

18、为不允许空盒，因此常数项为零，单独第一盒的母函数可构造为：一盒的母函数可构造为：x+x2+xn+其它盒也有同样的情况，共其它盒也有同样的情况，共m m个盒子。个盒子。盒第第二盒第一盒m .).).(.)()(222xxxxxxxG2.8：整数的拆分：整数的拆分23mmxx)1(.),1(.!2)1(1(2kmxkkmCxmmmxx xn-m项的系数是项的系数是:C(m+n-m-1,n-m)=C(n-1,n-m)=C(n-1,m-1)因此。方案数为因此。方案数为C(n-1,m-1)2.8：整数的拆分：整数的拆分*242.9 费勒斯（费勒斯（Ferrers)图像图像 假设正整数假设正整数n n拆分

19、成拆分成n=n1+n2+nk。其中其中n n1nn2 nn3 n nk。将他们排成阶。将他们排成阶梯形，左边对齐，第一行梯形，左边对齐，第一行n n1格，第二行格，第二行n n2格，格，第第k k行行n nk格。格。32211234例如：例如：8=3+2+2+18=3+2+2+11 1、什么是费勒斯图像、什么是费勒斯图像252 2、费勒斯（费勒斯（FerresFerres)图像的性质：图像的性质：(1)(1)每一层至少有一个格子；每一层至少有一个格子；(3)(3)行与列互换，即第行与列互换，即第1 1行与第行与第1 1列互换，列互换，第第2 2行与第行与第2 2列互换，列互换，,也就是沿对角线

20、旋也就是沿对角线旋转转180180，仍然是费勒斯图像；，仍然是费勒斯图像；后一个费勒斯图像称为前一个费勒斯后一个费勒斯图像称为前一个费勒斯图像的共轭图像，而且互为共轭。图像的共轭图像，而且互为共轭。2.9 费勒斯（费勒斯（Ferrers)图像图像 (2)(2)下一层的格数不多于上一层的格子下一层的格数不多于上一层的格子数；数；262.9 费勒斯（费勒斯（Ferrers)图像图像322112343、费勒斯图像对拆分数的讨论、费勒斯图像对拆分数的讨论例如：例如：8=3+2+2+18=3+2+2+127定理定理2.9.1 2.9.1 如下两种拆分方式的数的是相等的。如下两种拆分方式的数的是相等的。(

21、1)(1)把正整数把正整数n n拆分成拆分成m m个数的和的拆分数。个数的和的拆分数。(2)(2)把正整数把正整数n n拆分成最大数为拆分成最大数为m m的拆分数之和。的拆分数之和。推论推论:如下拆分数相同如下拆分数相同(1)(1)正整数正整数n n拆分成最多不超过拆分成最多不超过m m个数的和的个数的和的拆分数，拆分数，(2)(2)正整数正整数n n拆分成最大数不超过拆分成最大数不超过m m的数的拆的数的拆分数。分数。2.9 费勒斯（费勒斯（Ferrers)图像图像28定理定理2.9.1 2.9.1 如下两种拆分方式的数的是相等的。如下两种拆分方式的数的是相等的。(1)(1)把正整数把正整数

22、n n拆分成拆分成m m个数的和的拆分数。个数的和的拆分数。(2)(2)把正整数把正整数n n拆分成最大数为拆分成最大数为m m的拆分数之和。的拆分数之和。.12xx.142xx.163xx.mmxxxxx1.11111132.32mmmxxx2.9 费勒斯（费勒斯（Ferrers)图像图像29.12xx.142xx.163xx.mxxxx11.11111132.132mmmxxx推论推论:正整数正整数n n拆分成最多不超过拆分成最多不超过m m个数的和个数的和的拆分数，等于将的拆分数，等于将n n拆分成最大数不超过拆分成最大数不超过m m的的数的拆分数。数的拆分数。2.9 费勒斯（费勒斯（F

23、errers)图像图像30mxxxx11.11111132拆分成正好拆分成正好m m个数的拆分数。个数的拆分数。mmxxxxx1.11111132拆分成不超拆分成不超m m个数的拆分数。个数的拆分数。拆分成不超拆分成不超m-1m-1个数的拆分数。个数的拆分数。13211.111111mxxxx2.9 费勒斯（费勒斯（Ferrers)图像图像31 定理定理2.9.2 2.9.2 整数整数n n拆分成互不相同的若干拆分成互不相同的若干奇数和的拆分数，与奇数和的拆分数，与n n拆分成有自共轭费勒斯拆分成有自共轭费勒斯图像的拆分数相等。这里所讲的自共轭费勒图像的拆分数相等。这里所讲的自共轭费勒斯图像是

24、指共轭图像与原图像一致。斯图像是指共轭图像与原图像一致。每一个奇数都与右图这样的每一个奇数都与右图这样的自共轭费勒斯图像一一对应。自共轭费勒斯图像一一对应。n n拆分成若干奇数和可以如下表示：拆分成若干奇数和可以如下表示：n=(2nn=(2n1 1+1)+(2n+1)+(2n2 2+1)+1)+(2n+(2nk k+1)+1)任何一个奇数都可表示成任何一个奇数都可表示成2n+12n+1这种形式。这种形式。2.9 费勒斯（费勒斯（Ferrers)图像图像32 例如：例如：17=9+5+317=9+5+3，求所对应的自共轭，求所对应的自共轭费勒斯图像。费勒斯图像。首先将首先将9 9写成写成2 24

25、+1,4+1,按此构造自共轭按此构造自共轭费勒斯图像。费勒斯图像。将将5 5写成写成2 22+1,2+1,按此构造自共轭费勒按此构造自共轭费勒斯图像。斯图像。将将3 3写成写成2 21+1,1+1,按此构造自共轭费勒按此构造自共轭费勒斯图像。斯图像。将这三个图像结合起来就得到了我们将这三个图像结合起来就得到了我们所要求的图像。所要求的图像。2.9 费勒斯（费勒斯（Ferrers)图像图像33 n n拆分成若干奇数和可以如下表示：拆分成若干奇数和可以如下表示：n=(2nn=(2n1 1+1)+(2n+1)+(2n2 2+1)+1)+(2n+(2nk k+1)+1)构造一个构造一个FerrersF

26、errers图像，其第一行，图像，其第一行，第一列都是第一列都是n n1 1+1+1格，对应于格，对应于2n2n1 1+1+1，第二行，第二列各第二行，第二列各n n2 2+2+2格，对应格，对应于于2n2n2 2+1+1。以此类推。由此得到的以此类推。由此得到的FerresFerres图像图像是自共轭的。是自共轭的。2.9 费勒斯（费勒斯（Ferrers)图像图像34 例例1 1 若有若有1 1克、克、2 2克、克、3 3克、克、4 4克的砝码克的砝码各一枚，问能称出几种可能的重量。各一枚，问能称出几种可能的重量。解：解：单独单独1 1克砝码的母函数为克砝码的母函数为1+x1+x 单独单独2 2克砝码的母函数为克砝码的母函数为1+x1+x2 2，单独单独3 3克砝码的母函数为克砝码的母函数为1+x1+x3 3,单独单独4 4克砝码的母函数为克砝码的母函数为1+x1+x4 4。2.8：整数的拆分：整数的拆分 （1+x)(1+x2)(1+x3)(1+x4)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10