组合数学(24)

1、1第八章第八章 特殊计数序列特殊计数序列8.3 分拆数分拆数 所谓整数拆分即把整数分解成若干整数的所谓整数拆分即把整数分解成若干整数的和和，各部分不允许出现，各部分不允许出现0值值, 本次课我们将讨论本次课我们将讨论对整数对整数n的进行两类拆分的组合记数问题，一类的进行两类拆分的组合记数问题，一类是无限制地拆分，另一类是限制拆分块数量的是无限制地拆分，另一类是限制拆分块数量的拆分。把整数拆分成若干整数的和，办法不一，拆分。把整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做不同拆分法的总数叫做拆分数拆分数(或者或者分拆数分拆数)。2 设设n是一个正整数，若存在正整数的集合是一个正整数，若存

2、在正整数的集合 n1, n2, nk (其中其中1 k n，ni n)使得使得 n1 n2nkn则称则称 n1, n2, nk 是是n的一个的一个分拆分拆。分拆个数可以记为。分拆个数可以记为Pnk 如果如果n的一个分拆含有的一个分拆含有an个个n, an-1个个(n-1),a2个个2和和a1个个1。即。即: nnan + (n-1)an-1 + + 2a2 + 1a13则将该分拆则将该分拆 记作记作: 上述表示方法仅仅是个记号上述表示方法仅仅是个记号, 没有指数运没有指数运算的意义。算的意义。例如：例如：整数整数n 拆分方式拆分方式 拆分个数拆分个数Pnk 2， 2, 1+1 2个个 3, 3

3、, 2+1, 1+1+1 3个个 4, 4, 3+1, 2+2, 2+1+1, 1+1+1+1 5个个12112.) 1(aaaannnn4取整数取整数4来更换表示形式：它可以是来更换表示形式：它可以是1个个4；一一个个3和一个和一个1；两个两个2；一个；一个2和两个和两个1；四个四个1。这样，整数这样，整数4的分拆个数：的分拆个数： Pn1=P43=P44=1 ； P42= 2共计为共计为5 ； 同时同时4的分拆可以记为：的分拆可以记为： 41, 3111, 22, 2112, 14注意注意pn与与Pnk是两个不同概念的分拆数，是两个不同概念的分拆数， pn表示表示正整数正整数n的分拆数，没

4、有限制分拆的分拆数，没有限制分拆n后各类的后各类的数量；数量； Pnk表示分拆表示分拆n后各类的数量必须是后各类的数量必须是k个个5例如：将例如：将5分拆：分拆： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1， 1+1+1+1+1，共，共7个分拆，所以：个分拆，所以： pn=7而而Pnk 根据根据k值来分：值来分： k=1,2,3,.5;故分别有：故分别有： Pn1=1; Pn2=2; Pn3=2; Pn4=1; Pn5=1;令令pn表示正整数表示正整数n的总分拆数，为了方便起见，的总分拆数，为了方便起见， 把初值：把初值： p0 = 1 ，分拆数构成的序列为：，分拆数

5、构成的序列为： p0, p1, p2, p3, pn,. 6由前面的讨论我们已经有：由前面的讨论我们已经有： p0 = 1, p1 = 1, p2 = 2, p3 = 3, p4 = 5, 对上述序列我们讨论递推关系。对上述序列我们讨论递推关系。定理：定理：n分拆数分拆数Pnk满足下列递推关系：满足下列递推关系：证明：只证第一式，第二式表示将证明：只证第一式，第二式表示将n分拆成分拆成1个个部分和部分和n个部分，显然只有一种可能。个部分，显然只有一种可能。设设E是将是将n分成不多于分成不多于k个类的分拆的集合。个类的分拆的集合。1,11nnkjnkknjnPPPP7 属于属于E的每个分拆可看成

6、是一个的每个分拆可看成是一个k元组元组(其分量其分量 用用0补足补足k位位)。在。在E上定义映射上定义映射: (a)=a 。 a=(a1, a2, , am, 0, 0, , 0) a =(a1+1, a2+1, , am+1, 1, 1, , 1) 在此映射下，在此映射下，E被映入将被映入将n+k分成恰有分成恰有k个个类的分拆的集合类的分拆的集合E 。因此。因此:,) 1 (21212121aaEaaaaEaa8（2） 对对a E aE 使使 (a)=a 可见可见, 为一双射函数。因此：为一双射函数。因此： 注意到注意到 jn时有时有Pnj=0, 故对故对kn 有：有：利用定理给出的公式，可

7、递归地推算利用定理给出的公式，可递归地推算Pnk如下：如下：kknkjjnPEPE| |1njjnkknPP19Pnk k=1 2 3 4 5 6 7 8n=1 1 2 1 1 3 1 1 1 4 1 2 1 1 5 1 2 2 1 1 6 1 3 3 2 1 1 7 1 3 4 3 2 1 1 8 1 4 5 5 3 2 1 1 10 求拆分三角的算法求拆分三角的算法: 1 定义数组定义数组P=(1：n, 1：n);2 对对k=1, n, 做做 P(k, 1) 1; P(k, k) 1;3 打印打印P（1， 1）；）； 打印打印P（2， 1），）， P（2， 2）；）；4 对对i=3, n,

8、 做做 11 4.1 对对j=2, i-1, 做做 S 0; n1i-j; n2 min(j, n1); 对对t=1, n2, SS+P(n1, t); P(i, j)S; 4.2 对对j=2, i，做，做 按行打印按行打印P(i, j)； 5结束。结束。12观察公式：观察公式： pn等价于方程等价于方程:nan+(n-1)an-1+.+2a2+1a1=n的非负整数解的非负整数解 an,an-1,.,a2,a1的个数。的个数。令令为为n的分拆：的分拆： 及及 a1a2a3ak1 12112.) 1(aaaannnnknnan1例如：例如：10=10=9+1=8+2=8+1+1=7+3=7+2+

9、1=7+1+1+1=6+4=6+3+1=6+2+2=6+2+1+1=6+1+1+1+1=5+5=5+4+1=5+.13 由上面的例子看出，可以对分拆着两类化分：由上面的例子看出，可以对分拆着两类化分： 第一类型：以分拆成的各类数量为拆分标第一类型：以分拆成的各类数量为拆分标准；准； 第二类型：以分拆成的各类中最大的数为第二类型：以分拆成的各类中最大的数为拆分标准；拆分标准； 显然，拆分类中最大类的数越大，该类的数显然，拆分类中最大类的数越大，该类的数量就越少：将量就越少：将10分拆为分拆为9+1只有两类，而：只有两类，而： 10=2+1+1+1+1+1+1+1+1就有就有9类。类。14 我们把

10、我们把的的Ferrers图简单称为图简单称为图图。它是一个左。它是一个左 齐调整点组，该组有齐调整点组，该组有k行，第行，第i行有行有ni的点。的点。 例例:10的分拆的分拆 1042211可记作可记作 412212该分拆的图为该分拆的图为 : . . . . . . . . . . . . . . . . . . . .显然显然.对于任何正整数对于任何正整数n,它的它的每个分拆可以由图唯一确定。每个分拆可以由图唯一确定。如如10的分拆是的分拆是4221时，时，图为图为：15 将将的图看成一个矩阵的图看成一个矩阵,这个矩阵的转置矩阵这个矩阵的转置矩阵 称其为分拆称其为分拆的共轭分拆的共轭分拆,

11、记为记为*。 *的图与的图与的图互称为的图互称为共轭图共轭图。例如上图的共轭图是。例如上图的共轭图是: 它们分别表示的它们分别表示的10的分拆是的分拆是: = 4221; *=3222; . . . . . . . . . . 共轭图共轭图*图图 . . . . . . . . . . 的图的图16当某个分拆当某个分拆与它的共轭分拆与它的共轭分拆*完全相同时完全相同时: = *;或者说或者说的图是一个对称方阵时的图是一个对称方阵时,我我们把拆分们把拆分称为称为自共轭分拆自共轭分拆。例如：将例如：将12拆分成：拆分成：12= 4+4+2+2； = 4222; 其图如下：其图如下： 它的转置与自身

12、一样。它的转置与自身一样。 它关于主对角线对称。它关于主对角线对称。 . . . . . . . . . . . . 的图的图17 定理：定理：n的自共轭拆分的个数等于的自共轭拆分的个数等于n分成各类分成各类 都不相等且都是奇数的拆分的个数。都不相等且都是奇数的拆分的个数。 证明：设证明：设 ,其中其中n1n2nk。显见这是一个把显见这是一个把n分成各类都不相同且都是奇分成各类都不相同且都是奇数的拆分，对应的图的第数的拆分，对应的图的第i行有行有2ni+1个方格。个方格。构造一新的图，使其第构造一新的图，使其第i行及第行及第i列都是列都是ni+1个个方格。注意到交叉处的方格重合，故方格。注意到

13、交叉处的方格重合，故:kiinn1)12(18 这恰用掉原图的第这恰用掉原图的第i行的行的2ni+1个方格。而新构造个方格。而新构造 的图以对角线为轴线对称，的图以对角线为轴线对称， 即对应的拆分即对应的拆分是自共轭的。是自共轭的。 反之，对任一自共轭拆分，用其图中第反之，对任一自共轭拆分，用其图中第i行行及第及第j列的全部方格（共列的全部方格（共2ni+1个）作为新构造个）作为新构造的图的第的图的第i行，这新得到的图对应的拆分又是行，这新得到的图对应的拆分又是n分成各类都不相等且都是奇数的拆分。以上讨分成各类都不相等且都是奇数的拆分。以上讨论建立了两种拆分间的双射函数。论建立了两种拆分间的双

14、射函数。19定理：定理：n分成各类互不相同的拆分的个数分成各类互不相同的拆分的个数,等于等于n 分成各类都是奇数的拆分的个数。分成各类都是奇数的拆分的个数。 证明：设证明：设 ,其中其中ni为奇数，为奇数，ri为为ni的重的重复次数。注意到复次数。注意到rt可表示为可表示为 10,20ktkkktbbbr 断言断言 n= b020n1+b121n1+b020n2+b121n2+ +b020ni+b121ni+b020nj+b121nj+ 0tiinrn20中取掉中取掉0项（项（bk=0），就构成），就构成n的各类互不相等的各类互不相等 的拆分。事实上的拆分。事实上:tjsitijsiknnbn

15、bnbji222212 若若s=t，显见有，显见有ninj；若；若st（不妨设（不妨设ts）, 但但ni=nj2t-s， 这导致这导致ni为偶数，与题设矛盾，故为偶数，与题设矛盾，故断言为真。又上述构造过程的逆也成立。断言为真。又上述构造过程的逆也成立。 这这就建立了两种拆分间的双射函数。就建立了两种拆分间的双射函数。 21 由于共轭分拆通过转置得到，那么由于共轭分拆通过转置得到，那么*的个的个 数就等于数就等于 的最大部分。的最大部分。例如：例如：10 = 5+3+1+1； = 513112；图如下：；图如下： . . . . . . . . . . 的图的图 . . . . . . . .

16、 . . *的图的图 10的最大部分是的最大部分是5；图的第一行是图的第一行是5；转置后；转置后*图的第一列是五行，如同五个部分图的第一列是五行，如同五个部分*= 41221222定理：定理：n分成分成k个类的拆分的个数，等于个类的拆分的个数，等于n分成以分成以 k为最大类的拆分的个数。为最大类的拆分的个数。例如，当例如，当n=6时，以时，以3作为最大类的拆分有作为最大类的拆分有3个个:3+1+1+1， 3+2+1， 3+3而分成而分成3个类的拆分也有个类的拆分也有3个：个： 4+1+1， 3+2+1， 2+2+2 23 证明：考虑一个拆分：证明：考虑一个拆分： 例如例如11=5+4+1+1，

17、并构作一个相应的图，并构作一个相应的图，在图中每个类均表示成一行小点，每行的在图中每个类均表示成一行小点，每行的点数等于类本身的数目，考虑到拆分组的点数等于类本身的数目，考虑到拆分组的分量由左向右成一递减序列，故对应的图分量由左向右成一递减序列，故对应的图从上而下，各行点数也自然呈递减数列。从上而下，各行点数也自然呈递减数列。 . . . . . . . . . . . 图图24分拆数序列分拆数序列pn的生成函数的生成函数 定理定理8.3.1 n的拆分数的拆分数Pn的生成函数是：的生成函数是： )1()1()(10101jjnnnPxxpxG设证明：事实上，当证明：事实上，当|x|1时，等式的

18、右边的一般式：时，等式的右边的一般式： .).1 (.)1 (.)1 (.)1 (1)1 (1)1 (1)1 (1633342222113322111xaxaxaxaxaxaxaxaxaxajjj25展开式的系数中，常数项是展开式的系数中，常数项是1；一次项只能有乘；一次项只能有乘积的第一个因子中得到，从第二项开始积的第一个因子中得到，从第二项开始x的次的次数已经大于数已经大于2了；了；.；xn在的项，在的项， 由第一个因子选择由第一个因子选择 ,第二个因子选择第二个因子选择 等等确定；等等确定； xn项的幂有关系：项的幂有关系：nkjkjjkjjjjjjjjjxaaaxaxaxaxaxak)

19、(1)()()1 (1212110022011111xa222xa26最后，取最后，取a1=a2=1，即得公式：，即得公式： kkkk.2.221.1121 xn项的系数中的第一项项的系数中的第一项 确定确定n的一个拆分，即：的一个拆分，即：kkaaa2121nk.321)1()1()(10101jjnnnPxxpxG设27 定理定理8.3.2: n拆分拆分k类类的分拆数的分拆数Pnk的生成函数是的生成函数是: 该定理的证明与定理该定理的证明与定理8.3.1一样，同学们可以一样，同学们可以自己证明。自己证明。 定理定理8.3.3: n拆分成仅有奇数类拆分成仅有奇数类的分拆数的分拆数Pn的的生成

20、函数是生成函数是:112102)1 ()1 ()1 ()(kknnknxxxxxpxG)1)(1)(1 ()1 ()1 ()1 ()(1056321513103xxxxxxxxxxpxGnnn28定理定理8.3.4：n分成分成各类互不相等各类互不相等的拆分数的拆分数Pn的生的生 成函数是：成函数是：定理定理8.3.5：n分成分成各类互不相等的奇数类各类互不相等的奇数类的拆分的拆分 数数Pn的生成函数是：的生成函数是：实际上实际上G3(x) = G4(x) ,下面我们给于证明。下面我们给于证明。)1)(1)(1 ()(3204xxxxpxGnnn0125)1()(kkxxG29 证明：事实上我们

21、将证明：事实上我们将G3(x) 变形就得到变形就得到G4(x) ：)()1 ()1)(1)(1 ()1)(1)(1)(1)(1)(1 ()1 ()1 ()1 ()1 (1)()1 ()1 ()1 ()(4132332201212120123151313xGxxxxxxxxxxxxxxxGxxxxGjjjjjjjjjj30例例 1 有有1、2、3、4克的砝码各一枚，问能称出克的砝码各一枚，问能称出 哪几种重量？哪几种重量？ 对能称出的重量有几种可称对能称出的重量有几种可称量方案？量方案？解：解： 1098765432414222221)1 ()(xxxxxxxxxxxxGi 从从G(x)展开式中

22、展开式中x的幂次知，可称出的幂次知，可称出110克的重量，系数即为对应的称量方案数。如对克的重量，系数即为对应的称量方案数。如对2x5项，即称量项，即称量5克的方案有两种：克的方案有两种：31 5 = 3+2 = 4+1 同样，同样， 有有 6=1+2+3=4+2， 10=1+2+3+4 故称出故称出6克的方案数有两种，克的方案数有两种， 称出称出10克的方克的方案数是唯一的。案数是唯一的。例例2 求用求用1角，角，2角，角，3角的邮票贴出不同数值的角的邮票贴出不同数值的方案数。方案数。 解：因邮票允许重复，故生成函数为：解：因邮票允许重复，故生成函数为：32 以以x4为例，其系数为为例，其系

23、数为4，即，即4拆分成拆分成1、2、3之之和的拆分数为和的拆分数为4，拆分方案为：，拆分方案为：4=1+1+1+1， 4=1+1+2， 4=2+2， 4=1+3 njjjjjjnxxxxxxxxxxxxxxxG4321312113121030204321)1 ()1 ()1 (1)1 ()1 ()1 ()(33例例 3 若有若有1克的砝码克的砝码3枚枚,2克的砝码克的砝码4枚枚,4克的克的 砝码砝码2枚。问能称出哪些重量？有几种方案？枚。问能称出哪些重量？有几种方案？解：解： G(x)=(1+x+x2+x3)(1+x2+x4+x6+x8)(1+x4+x8) =(1+x+x2+2x3+2x4+2

24、x5+2x6+2x7+2x8+2x9+x10 +x11) (1+x4+x8)=1+x+2x2+2x3+3x4+3x5+4x6+4x7+5x8+5x9+5x10+5x11+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19 观察展开式各项中观察展开式各项中x的幂次及其系数即知答案。的幂次及其系数即知答案。34例例 4 整数整数n拆分成拆分成1，2，3，, m的和，并允许的和，并允许 重复，求其生成函数。若其中重复，求其生成函数。若其中m至少出现至少出现一次，其生成函数如何？一次，其生成函数如何？解：当解：当n允许重复地拆分成允许重复地拆分成1，2，m的和时，的和时，其生成

25、函数：其生成函数：mjmjjjjjxxxxxxxG111111)(20020135 若拆分中若拆分中m至少出现一次，其生成函数：至少出现一次，其生成函数：00202)(jmjjjjjxxxxG显见显见 G2(x)=G1(x)(1-xm)G1(x)= xmG1(x) 其组合意义是：其组合意义是：n拆分成拆分成1, 2, , m的和的的和的拆分数，拆分数， 减去减去n拆分成拆分成1, 2, , m-1的和的拆分的和的拆分数，数， 即为至少出现一个即为至少出现一个m的拆分数。的拆分数。36例例 5 设有设有1、 2、 4、 8、 16、32克砝码各一枚，克砝码各一枚， 问能称出哪些重量？问能称出哪些重量？ 分别有几种方案？分别有几种方案？解：解： 由生成函数知，用给定的砝码能称出从由生成函数知，用给定的砝码能称出从1克到克到63克的各种重量，且其方案都是唯一的。克的各种重量，且其方案都是唯一的。630643264163281648242321684211111111111111)1)(1)(1)(1)(1)(1 ()(kkxxxxxxxxxxxxxxxxxxxxxxG37有有 序序 拆拆 分分 以上讨论的关于整数以上讨论的关于整数n的拆分都是无序拆分。的拆分都是无序拆分。即在定义中强加了一种序即在定义中强加了一种序a1a2am1。或。或可视如可