组合数学教学课件44整数的拆分课件

把n个无区别的球分放在一些无区别的盒子中，究竟有多少种不同的放法?无区别的盒子意味着，如果有四个相同的球，则在第一个盒子中放入三个球，第二个盒子中放入一个球与第一个盒子中放入一个球，第二个盒子中放入三个球的放法是一样的。§4.4整数的拆分

作为母函数应用的一个实例，下面讨论把n个无区别的球放在一些无区别的盒子中的问题.§4.4整数的拆分作为母函数应用的一个实例，下面讨论把n如5=3+2和5=2+3被认为是同样的拆分法。显然整数n的一个拆分等价于把n个无区别的球分放在一些无区别的盒子中的一种方法。一个整数的拆分是把整数分拆为若干个正整数部分。而这些部分的次序是无关紧要的。一个整数的拆分是把整数分拆为若干个正整数

正整数n的拆分种数记作P(n)。例如，对于正整数n=1,2,3,4的拆分是n=1:1=1∴P(1)=1n=2:2=2,2=1+1∴P(2)=2n=3:3=3,3=2+1,3=1+1+1∴P(3)=3n=4:4=4,4=3+1,4=2+2,4=2+1+1,4=1+1+1+1∴P(4)=5正整数n的拆分种数记作P(n)。首先考虑恒等式于是有首先考虑恒等式于是有

在上式中可以看出xn的系数等于n拆分为1，2，3的和的方法数。例如x3的系数是3，这表示整数3拆分成1，2，3的和的方法数是3，即

3=3,3=2+1,3=1+1+1

又例如x4的系数是4，它表明有4种方法将4拆分为1，2，3的和。即4=3+1,4=2+2,4=2+1+1，4=1+1+1+1在上式中可以看出xn的系数等于n拆分为1，2，3的和在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,分别表示数字1没有被选，选一个1，选二个1，选三个1，……。同样的，因子(1+x2+x4+x6+…)则表示2没有被选，或选一个2，或选二个2，或选三个2，……。因子(1+x3+x6+x9+…)则表示3没有被选，或选一个3，或选二个3，或选三个3，……。这样，上面三个因子的乘积的xn的系数就是n拆分为1，2，3的和的方法数。

这与上面的例子是吻合的。由此我们可以分析如下：在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,

又如x6的系数是7，它表示6拆分为1，2，3的和的方法有7种，见表4-1。由此可见，函数1/(1-x)(1-x2)1-x3)的级数展开式中，xn的系数就等于把n拆分为1，2，3的和的方法数P(n)。注：表4－1见书69页。又如x6的系数是7，它表示6拆分为1，2，3的的级数展开式中的xn的系数等于把正整数n拆分成a,b,c,…的和的方法数P(n)。一般地，有下面的定理。定理4.2设a,b,c,…是大于0的正整数，则一般地，有下面的定理。定理4.2设a,b,c,…是大于0如果项xn是由x3a，xb,x2c,…的乘积所组成，则证明：如前所述，只需注意于是每当n可以拆分为a,b,c的和时，xn就会出现。这就证明了定理的结论。如果项xn是由x3a，xb,x2c,…的乘积所组成，则证

1.用Pk(n)表示n拆分成1,2,…，k的允许重复的方法数。

2.用Po(n)表示n拆分成奇整数的方法数。

3.用Pd(n)表示n拆分成不同的整数的方法数。

4.用Pt(n)表示n拆分成2的不同幂(即1，2，4，8，…)的方法数。定义4.7由上面的讨论和定理4.2即可得1.用Pk(n)表示n拆分成1,2,…，k的允许重推论1｛P3(n)｝的普通母函数是推论2｛Pk(n)｝的普通母函数是推论3｛P(n)｝的普通母函数是推论1｛P3(n)｝的普通母函数是推论2｛Pk(n)｝的普通在定理4.2中，令a,b,c,…是奇整数，我们又有推论4｛P0(n)｝的普通母函数是的级数展开式中xn项的系数就是把n拆分成a,b,c,…的和，且a,b,c,…最多只出现一次的方法数。定理4.3设a,b,c,…都是大于0的正整数，则在定理4.2中，令a,b,c,…是奇整数，我们又有推论4｛P由定理4.3即可得推论1｛Pd(n)｝的普通母函数是推论2｛Pt(n)｝的普通母函数是定理4.4(Euler)对于正整数n都有由定理4.3即可得推论1｛Pd(n)｝的普通母函数是推论2｛证明：上式的左端正好是Pd(n)的普通母函数(由定理4.3的推论1)，而上式的右端，可将分子分母的所有偶次幂约去就得到证明：上式的左端正好是Pd(n)的普通母函数(由定理4.3的以上我们证明了把n拆分成奇整数的和的方式数等于把n拆分成不相同的整数的和的方式数。这正好是P0(n)的普通母函数(由推论4)。∴Po(n)=Pd(n)这正好是P0(n)的普通母函数(由推论4)。∴Po(n)=P下面我们验证当n=7的情况。7=77=77=5+1+17=6+17=3+3+17=5+27=3+1+1+1+17=4+37=1+1+1+1+1+1+17=4+2+1∴Po(7)=5Pd(7)=5

于是Po(7)=Pd(7)。下面我们验证当n=7的情况。定理4.5(Sylvester)

对正整数n，有Pt(n)=1证明：我们知道，任何正整数都可唯一地用一个二进制数来表示，而一个二进制数又可唯一地表成2的幂的和。由此即得结论。定理4.5(Sylvester)证明：我们知道，任何正如正整数39可以表成

39=100111=20+21+22+25下面用另一种方法来证明定理4.5。如正整数39可以表成下面用另一种方法来证明定理4.5。我们知道，序列(1，1，…，1)的普通母函数是又我们知道，序列(1，1，…，1)的普通母函数是又

而上式右端是Pt(n)的普通母函数(由定理4.3的推论2)定理证毕。而上式右端是Pt(n)的普通母函数(由

并用整数拆分的说法，这个恒等式的组合意义是什么?例1证明恒等式例1证明恒等式证明：而左端证明：而左端因此，这个恒等式表明，任何正整数都可唯一地拆分成形式为例如，对于整数349有唯一的拆分：349=9·100+4·101+3·102的不同部分。换句话说，任何整数的十进制表示是唯一的。因此，这个恒等式表明，任何正整数都可唯一地拆分成形式

通常，对于大的n，要求出将n拆分成某些整数的和的方式数P(n)是很困难的，但在有些问题中并不需要P(n)的精确值，只需P(n)的估计式就够了。下面的定理就给出了P(n)的估计式。通常，对于大的n，要求出将n拆分成某些整数的和证明：由推论3知｛P(n)｝的普通母函数为定理4.6对于任何正整数n,有将上式两边取对数得由对数的泰勒展开式知证明：由推论3知｛P(n)｝的普通母函数为定理4.6对于任于是有即故有

对于，设，则有于是有即故有对于，设将上面的不等式代入（A）式有而将上面的不等式代入（A）式有而而对于w>1时，有而对于w>1时，有于是有将以上结果代入（B）式得在上式中，令，则有所以有证毕。于是有

下面，我们讨论与整数拆分有着密切关系的Ferrers图。

这个定理的估计式还可以进一步加以改进。现在，已经有人证明了近似式：

设n的一个拆分为

n=a1+a2+…+ak

并假设a1≥a2≥a3≥…≥ak≥1。这个定理的估计式还可以进一步加以改进。现在，已

下面画一个图,这个图由一行行的点所组成。在第一行有a1个点，第二行有a2个点，

……，第k行有ak个点，称这图为Ferrers图。

整数的拆分可以用一个Ferrers图来表示，例如16=6+5+3+1+1的Ferrers图如图4-1下面画一个图,这个图由一行行的点所组成。

当给定Ferrers图后，可以将它的行与列对换，这就得到另一个图。显然，这个图也是一个Ferrers图。也就是说，一个Ferrers图的行与列对换所得的图仍是一个Ferrers图。

如图4-1作行与列的对换就得到图4-2。称图4-2为图4-1的共轭图。这个图表示整数16的另一个拆分：16=5+3+3+2+2+1当给定Ferrers图后，可以将它的行与列对换，

由此可见，n的一个拆分对应唯一的一个Ferrers图，反过来，一个Ferrers图又对应

一个n的唯一拆分。所以n的一个拆分同它的Ferrers图之间是一一对应的。由此可见，n的一个拆分对应唯一的一个F

证明：只须考虑Ferrers图和它的共轭图之间的关系，本定理结论即可得证。例如，对n=24,如图4-3(书75页)定理4.7正整数n拆分成m项的和的方式数等于n拆分成最大数为m的方式数。定理4.7正整数n拆分成m项的和的方式数等于n拆

定理4.8正整数n拆分成最多不超过m个项的和的方式数等于n拆分成最大的数不超过m的方式数。证明：留作练习。定理4.8正整数n拆分成最多不超过m个项的和的方式数等

把n个无区别的球分放在一些无区别的盒子中，究竟有多少种不同的放法?无区别的盒子意味着，如果有四个相同的球，则在第一个盒子中放入三个球，第二个盒子中放入一个球与第一个盒子中放入一个球，第二个盒子中放入三个球的放法是一样的。§4.4整数的拆分

作为母函数应用的一个实例，下面讨论把n个无区别的球放在一些无区别的盒子中的问题.§4.4整数的拆分作为母函数应用的一个实例，下面讨论把n如5=3+2和5=2+3被认为是同样的拆分法。显然整数n的一个拆分等价于把n个无区别的球分放在一些无区别的盒子中的一种方法。一个整数的拆分是把整数分拆为若干个正整数部分。而这些部分的次序是无关紧要的。一个整数的拆分是把整数分拆为若干个正整数

正整数n的拆分种数记作P(n)。例如，对于正整数n=1,2,3,4的拆分是n=1:1=1∴P(1)=1n=2:2=2,2=1+1∴P(2)=2n=3:3=3,3=2+1,3=1+1+1∴P(3)=3n=4:4=4,4=3+1,4=2+2,4=2+1+1,4=1+1+1+1∴P(4)=5正整数n的拆分种数记作P(n)。首先考虑恒等式于是有首先考虑恒等式于是有

在上式中可以看出xn的系数等于n拆分为1，2，3的和的方法数。例如x3的系数是3，这表示整数3拆分成1，2，3的和的方法数是3，即

3=3,3=2+1,3=1+1+1

又例如x4的系数是4，它表明有4种方法将4拆分为1，2，3的和。即4=3+1,4=2+2,4=2+1+1，4=1+1+1+1在上式中可以看出xn的系数等于n拆分为1，2，3的和在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,分别表示数字1没有被选，选一个1，选二个1，选三个1，……。同样的，因子(1+x2+x4+x6+…)则表示2没有被选，或选一个2，或选二个2，或选三个2，……。因子(1+x3+x6+x9+…)则表示3没有被选，或选一个3，或选二个3，或选三个3，……。这样，上面三个因子的乘积的xn的系数就是n拆分为1，2，3的和的方法数。

这与上面的例子是吻合的。由此我们可以分析如下：在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,

又如x6的系数是7，它表示6拆分为1，2，3的和的方法有7种，见表4-1。由此可见，函数1/(1-x)(1-x2)1-x3)的级数展开式中，xn的系数就等于把n拆分为1，2，3的和的方法数P(n)。注：表4－1见书69页。又如x6的系数是7，它表示6拆分为1，2，3的的级数展开式中的xn的系数等于把正整数n拆分成a,b,c,…的和的方法数P(n)。一般地，有下面的定理。定理4.2设a,b,c,…是大于0的正整数，则一般地，有下面的定理。定理4.2设a,b,c,…是大于0如果项xn是由x3a，xb,x2c,…的乘积所组成，则证明：如前所述，只需注意于是每当n可以拆分为a,b,c的和时，xn就会出现。这就证明了定理的结论。如果项xn是由x3a，xb,x2c,…的乘积所组成，则证

1.用Pk(n)表示n拆分成1,2,…，k的允许重复的方法数。

2.用Po(n)表示n拆分成奇整数的方法数。

3.用Pd(n)表示n拆分成不同的整数的方法数。

4.用Pt(n)表示n拆分成2的不同幂(即1，2，4，8，…)的方法数。定义4.7由上面的讨论和定理4.2即可得1.用Pk(n)表示n拆分成1,2,…，k的允许重推论1｛P3(n)｝的普通母函数是推论2｛Pk(n)｝的普通母函数是推论3｛P(n)｝的普通母函数是推论1｛P3(n)｝的普通母函数是推论2｛Pk(n)｝的普通在定理4.2中，令a,b,c,…是奇整数，我们又有推论4｛P0(n)｝的普通母函数是的级数展开式中xn项的系数就是把n拆分成a,b,c,…的和，且a,b,c,…最多只出现一次的方法数。定理4.3设a,b,c,…都是大于0的正整数，则在定理4.2中，令a,b,c,…是奇整数，我们又有推论4｛P由定理4.3即可得推论1｛Pd(n)｝的普通母函数是推论2｛Pt(n)｝的普通母函数是定理4.4(Euler)对于正整数n都有由定理4.3即可得推论1｛Pd(n)｝的普通母函数是推论2｛证明：上式的左端正好是Pd(n)的普通母函数(由定理4.3的推论1)，而上式的右端，可将分子分母的所有偶次幂约去就得到证明：上式的左端正好是Pd(n)的普通母函数(由定理4.3的以上我们证明了把n拆分成奇整数的和的方式数等于把n拆分成不相同的整数的和的方式数。这正好是P0(n)的普通母函数(由推论4)。∴Po(n)=Pd(n)这正好是P0(n)的普通母函数(由推论4)。∴Po(n)=P下面我们验证当n=7的情况。7=77=77=5+1+17=6+17=3+3+17=5+27=3+1+1+1+17=4+37=1+1+1+1+1+1+17=4+2+1∴Po(7)=5Pd(7)=5

于是Po(7)=Pd(7)。下面我们验证当n=7的情况。定理4.5(Sylvester)

对正整数n，有Pt(n)=1证明：我们知道，任何正整数都可唯一地用一个二进制数来表示，而一个二进制数又可唯一地表成2的幂的和。由此即得结论。定理4.5(Sylvester)证明：我们知道，任何正如正整数39可以表成

39=100111=20+21+22+25下面用另一种方法来证明定理4.5。如正整数39可以表成下面用另一种方法来证明定理4.5。我们知道，序列(1，1，…，1)的普通母函数是又我们知道，序列(1，1，…，1)的普通母函数是又

而上式右端是Pt(n)的普通母函数(由定理4.3的推论2)定理证毕。而上式右端是Pt(n)的普通母函数(由

并用整数拆分的说法，这个恒等式的组合意义是什么?例1证明恒等式例1证明恒等式证明：而左端证明：而左端因此，这个恒等式表明，任何正整数都可唯一地拆分成形式为例如，对于整数349有唯一的拆分：349=9·100+4·101+3·102的不同部分。换句话说，任何整数的十进制表示是唯一的。因此，这个恒等式表明，任何正整数都可唯一地拆分成形式

通常，对于大的n，要求出将n拆分成某些整数的和的方式数P(n)是很困难的，但在有些问题中并不需要P(n)的精确值，只需P(n)的估计式就够了。下面的定理就给出了P(n)的估计式。通常，对于大的n，要求出将n拆分成某些整数的和证明：由推论3知｛P(n)｝的普通母函数为定理4.6对于任何正整数n,有将上式两边取对数得由对数的泰勒展开式知证明：由推论3知｛P(n)｝的普通母函数为定理4.6对于任于是有即故有

对于，设，则有于是有即故有对于，设将上面的不等式代入（A）式有而将上面的不等式代入（A）式有而而对于w>1时，有而对于w>1时，有于是有将以上结果代入（B）式得在上式中，令，则有所以有证毕。于是有

下面，我们讨论与整数拆分有着密切关系的Ferrers图。

这个定理的估计式还可以进一步加以改进。现在，已经有人证明了近似式：