组合数学第二章第九节

1、2.9 2.9 费勒斯（费勒斯（FerrersFerrers) )图像图像 假设正整数假设正整数n n拆分成拆分成n=nn=n1 1+n+n2 2+ +n+nk k。 其中其中n n1 1nn2 2 nn3 3 n nk k。将他们排成。将他们排成阶梯形，左边对齐，第一行阶梯形，左边对齐，第一行n n1 1格，第二行格，第二行n n2 2格，格，第第k k行行n nk k格。格。32211234例如：例如：8=3+2+2+18=3+2+2+11 1、什么是费勒斯图像、什么是费勒斯图像2 2、费勒斯（费勒斯（FerresFerres) )图像的性质图像的性质：(1)(1)每一层至少有一个格子；每

2、一层至少有一个格子； (3)(3)行与列互换，即第行与列互换，即第1 1行与第行与第1 1列互换，列互换，第第2 2行与第行与第2 2列互换，列互换，, ,也就是沿对角线旋也就是沿对角线旋转转180180，仍然是费勒斯图像；，仍然是费勒斯图像； 后一个费勒斯图像称为前一个费勒斯后一个费勒斯图像称为前一个费勒斯图像的共轭图像，而且互为共轭。图像的共轭图像，而且互为共轭。 (2)(2)下一层的格数不多于上一层的格子下一层的格数不多于上一层的格子数；数； (1) 整数整数n拆分成拆分成k个数的和的拆分数，与数个数的和的拆分数，与数n拆分成拆分成最大数为最大数为k的拆分数相等。的拆分数相等。因为整数因

3、为整数n拆分成拆分成k个数的和的拆分可以用一个个数的和的拆分可以用一个k行行的图像表示。所得的的图像表示。所得的Ferrers图像的共轭图像最上面图像的共轭图像最上面一行有一行有k个格子。例如：个格子。例如： 3. 利用利用Ferrers图像可以得到一些关于整数拆分的结果：图像可以得到一些关于整数拆分的结果： 24=6+6+5+4+3 5个数，最大数为个数，最大数为6 24=5+5+5+4+3+2 6个数，最大数为个数，最大数为5理由和理由和(1)相类似。相类似。因此，拆分成最多不超过因此，拆分成最多不超过m个数的和的拆分数的母个数的和的拆分数的母函数是：函数是：(2) 整数整数n拆分成最多不

4、超过拆分成最多不超过m个数的和的拆分数，个数的和的拆分数，与与n拆分成最大不超过拆分成最大不超过m的拆分数相等。的拆分数相等。.()()()mxxx21111正好拆分成正好拆分成m个数的和的拆分数的母函数为个数的和的拆分数的母函数为()()()()()()mmxxxxxx 22111111111.()()()mmxxxx 2111(3) 整数整数n拆分成互不相同的若干奇数的和的的拆拆分成互不相同的若干奇数的和的的拆分数，与分数，与n拆分成自共轭的拆分成自共轭的Ferrers图像的拆分数图像的拆分数相等。相等。设整数设整数n拆分为拆分为n=(2n1+1)+(2n2+1)+(2nk+1)，其，其中

5、中n1n2nk。构造一个构造一个Ferrers图像，第一行第一列都是图像，第一行第一列都是n1+1格，格，对应于对应于2n1+1，第二行第二列都是，第二行第二列都是n2+1格，对应于格，对应于 2n2+1，依此类推。，依此类推。这样得到的这样得到的Ferrers图像一定是自共轭的。图像一定是自共轭的。反过来，自共轭的反过来，自共轭的Ferrers图像也可以对应到一些不图像也可以对应到一些不同奇数的和。同奇数的和。例如例如17=9+5+3对应的对应的Ferrers图像为：图像为：(4) 正整数正整数n剖分成不超过剖分成不超过k个数的和的剖分数，等于个数的和的剖分数，等于将将n+k剖分成恰好剖分成

6、恰好k个数的剖分数。个数的剖分数。不超过不超过k层的层的Ferrers图像的每一层加上一个格子，图像的每一层加上一个格子，一一对应到一个刚好一一对应到一个刚好k层的层的Ferrers图像。图像。2.11 指数型母函数指数型母函数考虑考虑n个元素组成的多重集，其中个元素组成的多重集，其中a1重复了重复了n1次，次，a2 重复了重复了n2次，次，ak重复了重复了nk次，次，n=n1+n2+nk。从中取从中取r个排列，求不同的排列数。个排列，求不同的排列数。若若r=n，即考虑，即考虑n个元素的全排列，则不同的排列数个元素的全排列，则不同的排列数为：为：!knn nn12但是对于一般的但是对于一般的r

7、，情况就比较复杂了。，情况就比较复杂了。876543232543232232369109631 )1 ( )23321 ( )1)(1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxG 先看一个具体的问题：假设有先看一个具体的问题：假设有8个元素，其中个元素，其中a1重重复复3次，次，a2重复重复2次，次，a3重复重复3次。从中取次。从中取r个组合，个组合，其组合数为其组合数为cr，则其对应的母函数为：，则其对应的母函数为：从从x4的系数可知，从这的系数可知，从这8个元素中取个元素中取4个组合，不同个组合，不同的组合数为的组合数为10。这这10个组合可从下面的展开式中得到：个组

8、合可从下面的展开式中得到： ()()()xxxxxxxx2322311122333111其中其中4次方项表示了所有从次方项表示了所有从8个元素中取个元素中取4个的组合个的组合方案。方案。例如例如 表示一个表示一个a1三个三个a3的组合，的组合， 表示两个表示两个a1两个两个a3的组合，依此类推。的组合，依此类推。331xx2321xx()( )( )( )xxxxx xxx xx xxxx xx xx xx x xx xx xx xxx xx xx xx x xx xx xx x xx x xx xx x221231122133322223311212131232223332223132331

9、323132223223123231212312313221211接下来讨论从这接下来讨论从这8个元素中取个元素中取4个的不同排列总数。个的不同排列总数。以两个以两个a1两个两个a3组合为例，不同排列数为组合为例，不同排列数为4!/(2!2!)。同样一个同样一个a1三个三个a3的不同排列数为的不同排列数为4!/(1!3!)。依此类推可以得到不同的排列总数为：依此类推可以得到不同的排列总数为：! ! ! ! ! ! ! ! ! ! ! ! ! !1111111 31 32 21 1 22 23 1411112 1 11 2 13 12 2.16183670( )()()()!exxxxxxxxG

10、x 2322311112312123为了便于计算，利用上述特点，形式地引进函数为了便于计算，利用上述特点，形式地引进函数xxxxxxxx23456789143517358113231212727272! .!xxxxxxxx2345678392870112341703505605605678从右边很容易可以看出，取从右边很容易可以看出，取2个的排列数为个的排列数为9，取，取3个个的排列数为的排列数为28，取，取4个的排列数为个的排列数为70依此类推。依此类推。定义定义：对于序列：对于序列a0,a1,a2,，函数，函数( ) !kkeaaaaGxaxxxxk233120123称为序列称为序列a0

11、,a1,a2,对应的对应的指数型母函数指数型母函数。这样，对于一个多重集，其中这样，对于一个多重集，其中a1重复重复n1次，次，a2 重复重复n2次，次，ak重复重复nk次，从中取次，从中取r个排列的不同排列个排列的不同排列数所对应的指数型母函数为：数所对应的指数型母函数为：( ) ! .!knennkxxxGxnxxxxxxnn1221222112111212例例1 求下列数列的指数型母函数：求下列数列的指数型母函数：( )(, );( );( ).nnnnaP m naab 1213( )( )(, )(, )() .!nmnmennxGxP m nC m n xxn 0011( )( )

12、.!nnbxenxGxben 03( )( ).!nxenxGxen 021例例2 由由1，2，3，4四个数字组成的五位数中，要求四个数字组成的五位数中，要求数数1出现次数不超过出现次数不超过2次，但不能不出现；次，但不能不出现； 2出现次出现次数不超过数不超过1次；次； 3出现次数最多出现次数最多3次，可以不出现；次，可以不出现；4出现次数为偶数。求满足上述条件的数的个数。出现次数为偶数。求满足上述条件的数的个数。( ) ()1! !exxxxxGxxxx22324112123124设满足上述条件的设满足上述条件的r位数个数为位数个数为cr，则其对应的指数，则其对应的指数型母函数为：型母函数

13、为： xxxxxxxxxx23456789105843433232448171114828848288! .!xxxxxxxxxx234567891051864215645123456178514076501260078910由此可见满足条件的由此可见满足条件的5位数共位数共215个。个。例例3 求由求由1，3，5，7，9五个数字组成的五个数字组成的n位数的个位数的个数，要求其中数，要求其中3，7出现的次数为偶数，其他出现的次数为偶数，其他1，5，9出现次数不加限制。出现次数不加限制。( ) !exxxxGxx 232423112423设满足上述条件的设满足上述条件的n位数个数为位数个数为cn

14、，则其对应的指，则其对应的指数型母函数为：数型母函数为： xxxeee 232( )()xxxeGxeee 223124()xxxeee53124().!nnnnxn 0152 314!nnnnnnnnxxxnnn00015324().nnna 152 314因此因此例例4 7个有区别的球放进个有区别的球放进4个有标志的盒子里，要求个有标志的盒子里，要求1，2两个盒子必须有偶数个球，第两个盒子必须有偶数个球，第3个盒子有奇数个个盒子有奇数个球，求不同的方案个数。球，求不同的方案个数。( )!exxxxxxGx 2243211241312这相当于从这相当于从1234这这4个数中取个数中取7个做允

15、许重复的排列，个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。即每个数字对应于每个球所放的盒子的序号。xxxxxeeeee 222这样的排列数所对应的指数型母函数为：这样的排列数所对应的指数型母函数为：( )()xxxeGxeee 422118().!nnnnnxn 1114228(),nnnna 14228因此因此().a 7777142220808例例5 r个有标志的球放进个有标志的球放进n个不同的盒子里，要求无一个不同的盒子里，要求无一空盒，问有多少种不同的分配方案？空盒，问有多少种不同的分配方案？( )!nexxxGx23123这相当于从这相当于从1到到n这这n个数字中取个数字中