1、 把把n n个无区别的球分放在一些无区别的盒子中，个无区别的球分放在一些无区别的盒子中，究竟有多少种不同的放法究竟有多少种不同的放法?无区别的盒子意味着，如果有四个相同的球，则无区别的盒子意味着，如果有四个相同的球，则在第在第一一个盒子中放入三个球，个盒子中放入三个球，第第二二个盒子中放入一个球与第一个盒子中放个盒子中放入一个球与第一个盒子中放入一个球，第入一个球，第二二个盒子中放入三个球的放法是个盒子中放入三个球的放法是一样的。一样的。4.44.4整数的拆分整数的拆分 作为母函数应用的一个实例，下面讨论把n个无区别的球放在一些无区别的盒子中的问题.如5=3+2和5=2+3被认为是同样的拆分法
2、。显然整数n的一个拆分等价于把n个无区别的球分放在一些无区别的盒子中的一种方法。一个整数的拆分是把整数分拆为若干个正整数部分。而这些部分的次序是无关紧要的。正整数n的拆分种数记作P(n)。例如例如，对于正整数n=1,2,3,4的拆分是 n=1:1=1 P(1)=1 n=2:2=2,2=1+1 P(2)=2 n=3:3=3,3=2+1,3=1+1+1 P(3)=3 n=4:4=4,4=3+1,4=2+2,4=2+1+1,4=1+1+1+1 P(4)=5首先考虑恒等式首先考虑恒等式3963264232111111111xxxxxxxxxxxx )1)(1)(1()1)(1)(1(16342232
3、xxxxxxxxx 65432754321xxxxxx于是有于是有 在上式中可以看出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在因子(1+x+x2+x3+)中的1,x,x2,x3,分别表示数 字1没有被选，选一个1，选二个1，选三个1，。同样的同样的，因子(1+x2+x4+x6+)则表示2没有被选，或选一个2，或选二个2，或选三个2，。因子(1+x3+x6+x9+
4、)则表示3没有被选，或选一个3，或选二个3，或选三个3，。这样，上面三个因子的乘积的xn的系数就是n拆分为1，2，3的和的方法数。这与上面的例子是吻合的。由此我们可以分析如下：这与上面的例子是吻合的。由此我们可以分析如下：又如x6的系数是7，它表示6拆分为1，2，3的和的方法有7种，见表表4-1。由此可见，函数1/(1-x)(1-x2)1-x3)的级数展开式中，xn的系数就等于把n拆分为1，2，3的和的方法数P(n)。注：注：表表4 41 1见书见书6969页。页。的级数展开式中的xn的系数等于把正整数n拆分成a,b,c,的和的方法数P(n)。)1)(1)(1(1cbaxxx 一般地，有下面的
5、定理。一般地，有下面的定理。设a,b,c,是大于0的正整数，则如果项xn是由x3a，xb,x2c,的乘积所组成，则)1)(1)(1(1cbaxxx )1)(1)(1(222 ccbbaaxxxxxx ccbaaan证明证明：如前所述，只需注意于是每当n可以拆分为a,b,c的和时，xn就会出现。这就证明了定理的结论。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.74.7由上面的讨论和定理4.2即可得)1)(1
6、)(1(132xxx )1()1)(1(12kxxx )1)(1)(1(132xxx 推论推论1 1P3(n)的普通母函数是推论推论2 2Pk(n)的普通母函数是推论推论3 3P(n)的普通母函数是)1)(1)(1)(1(1753xxxx )1)(1)(1(cbaxxx 在定理4.2中，令a,b,c,是奇整数，我们又有推论推论4 4P0(n)的普通母函数是的级数展开式中xn项的系数就是把n拆分成a,b,c,的和，且a,b,c,最多只出现一次的方法数。定理定理4.3 4.3 设a,b,c,都是大于0的正整数，则)1)(1)(1)(1(432xxxx )1)(1)(1)(1(842xxxx )()
7、(0npnpd 由定理由定理4.3即可得即可得推论推论1 1Pd(n)的普通母函数是推论推论2 2Pt(n)的普通母函数是定理定理4.4 4.4(Euler)对于正整数n都有,111,111111,1114843632422xxxxxxxxxxxx 483624243211111111)1)(1)(1)(1(xxxxxxxxxxxx )1)(1)(1)(1(1753xxxx 证明：证明：上式的左端正好是Pd(n)的普通母函数(由定理4.3的推论1)，而上式的右端，可将分子分母的所有偶次幂约去就得到以上我们证明了把n拆分成奇整数的和的方式数等于把n拆分成不相同的整数的和的方式数。这正好是P0(n
8、)的普通母函数(由推论4)。Po(n)=Pd(n)下面我们验证当n=7的情况。7=7 7=77=5+1+1 7=6+17=3+3+1 7=5+27=3+1+1+1+1 7=4+37=1+1+1+1+1+1+1 7=4+2+1Po(7)=5 Pd(7)=5 于是Po(7)=Pd(7)。定理定理4.5 4.5 (Sylvester)对正整数n，有 Pt(n)=1 证明：我们知道，任何正整数都可唯一地用一个二进制数来表示，而一个二进制数又可唯一地表成2的幂的和。由此即得结论。如正整数39可以表成 39=100111=20+21+22+25下面用另一种方法来证明定理4.5。我们知道，序列(1，1，1)
9、的普通母函数是 32111xxxx2422816484824816248248111,111111,1,111111(1)(1)(1)(1)1111xxxxxxxxxxxxxxxxxxxxxxxx x 11又又 而上式右端是Pt(n)的普通母函数(由定理4.3的推论2)1)(1)(00 npxxnptnnnnt定理证毕。定理证毕。并用整数拆分的说法，这个恒等式的组合意义是什么?)1()1)(1)(1(111091021090020010090201092kkkxxxxxxxxxxxxx 证明恒等式右右端端 )1()1()1)(1(11111111111091021090020010010910
10、210921010100100010100101kkkkkkkkxxxxxxxxxxxxxxxxxxxxx 32111xxxx证明：证明：而而 左端左端 因此因此，这个恒等式表明，任何正整数都可唯一地拆分成形式为,2,1,0;,2,1,10 nkkn例如，对于整数349有唯一的拆分：349=9100+4101+3102的不同部分。换句话说，任何整数的十换句话说，任何整数的十进制表示是唯一的。进制表示是唯一的。通常，对于大的n，要求出将n拆分成某些整数的和的方式数P(n)是很困难的，但在有些问题中并不需要P(n)的精确值，只需P(n)的估计式就够了。下面的定理就给出了P(n)的估计式。证明证明：
11、由推论3知P(n)的普通母函数为)1)(1)(1(1)(32xxxxf nenp3)()1log()1log()1log()(log32xxxxf 32)1log(32yyyy定理定理4.6 4.6 对于任何正整数n,有将上式两边取对数得将上式两边取对数得由对数的泰勒展开式知由对数的泰勒展开式知 )32()32()32()(log96364232xxxxxxxxxxf )1(31)1(211)333()222()(332296364232xxxxxxxxxxxxxxxnnxx 1)1,0(xnxxxxnn1211 于是有于是有即即故有故有 对于 ，设 ，则有1221 xxxxnnnxxxxnn
12、11121 将上面的不等式代入（将上面的不等式代入（A A）式有）式有xxnxxxxxxxxxxnnnnnn 111 111121故有故有 22223121111311211)(logxxxxxxxxxf而而xnxxxnxfnpxnpxnpxfxxxfdxxnnnlog12log)(log)(log)()()(12)(log2113121101222 故有故有而而故有故有由于由于1log ww而对于而对于w1时，有时，有 于是有 将以上结果代入（B）式得 在上式中，令 ，则有 所以有 证毕。xxxxx 1111loglog xxnxxnp112)(log1 nnxnenp3)(nnp3)(lo
13、g 下面，我们讨论与整数拆分有着密切关系的Ferrers图。nenp3/2341)(这个定理的估计式还可以进一步加以改进。现在，已经有人证明了近似式：设设 n的一个拆分为 n=a1+a2+ak 并假设a1a2a3ak1。下面画一个图,这个图由一行行的点所组成。在第一一行有a1个点，第二二行有a2个点，第k行有ak个点，称这图为Ferrers图。整数的拆分可以用一个Ferrers图来表示，例如16=6+5+3+1+1的Ferrers图如图4-1 当给定Ferrers图后，可以将它的行与列对换，这就得到另一个图。显然，这个图也是一个Ferrers图。也就是说，一个Ferrers图的行与列对换所得的
14、图仍是一个Ferrers图。如如图4-1作行与列的对换就得到图4-2。称图4-2为图4-1的共轭图。这个图表示整数16的另一个拆分：16=5+3+3+2+2+1 由此可见，n的一个拆分对应唯一的一个Ferrers图，反过来，一个Ferrers图又对应 一个n的唯一拆分。所以n的一个拆分同它的Ferrers图之间是一一对应的。证明证明：只须考虑Ferrers图和它的共轭图之间的关系，本定理结论即可得证。例如，对n=24,如图4-3(书书75页页)定理定理4.74.7正整数n拆分成m项的和的方式数等于n拆分成最大数为m的方式数。定理定理4.8 4.8 正整数n拆分成最多不超过m个项的和的方式数等于n拆分成最大的数不超过m的方式数。证明：留作练习。
