组合数学（第二版）母函数及其应用

母函数及其应用2.1母函数2.2母函数的性质2.3指数型母函数2.4正整数的分拆

在第一章中,已经解决了部分排列组合方案的计数问题.但对于不尽相异元素的部分排列和组合,用第一章的方法是比较麻烦的(参见表2.0.1).若改用母函数方法,问题将显得容易多了.其次,在求解递推关系的解、整数分拆以及证明组合恒等式时,母函数方法是一种非常重要的手段.

2.1母函数

定义2.1.1对于数列{an},称无穷级数为该数列的普通型母函数,简称普母函数或母函数,同时称{an}为G(x)的生成数列.

【例2.1.1】有限数列C(n,r),r=0,1,2,…,n的普母函数是(1+x)n.

【例2.1.2】无限数列{1,1,…,1,…}的普母函数是

说明

(1)an的非零值可以为有限个或无限个;

(2)数列{an}与母函数一一对应,即给定数列便得知它的母函数;反之,求得母函数则数列也随之而定;

(3)这里将母函数只看作一个形式函数,目的是利用其有关运算性质完成计数问题,故不考虑“收敛问题”,即始终认为它是收敛的,而且是可“逐项微分”和“逐项积分”的.

表2.1.1是一些常用的母函数,它们的证明只要利用解析函数展开成幂级数的方法即可得到.

定理2.1.1组合的母函数:设S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,则S的r可重组合的母函数为

其中,r可重组合数为xr之系数ar,r=0,1,2,…,n.

定理2.1.1的最大优点在于:

(1)将无重组合与重复组合统一起来处理;

(2)使处理可重组合的枚举问题变得非常简单.

推论6设S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,要求元素ei至少出现ki

次,则S的r可重组合的母函数为

【例2.1.3】设有2个红球,1个黑球,1个白球,问:

(1)共有多少种不同的选取方法.试加以枚举.

(2)若每次从中任取3个,有多少种不同的取法.

【例2.1.4】有18张戏票分给甲、乙、丙、丁4个班(不考虑座位号),其中,甲、乙两班最少1张,甲班最多5张,乙班最多6张;丙班最少2张,最多7张;丁班最少4张,最多10张.可有多少种不同的分配方案?

【例2.1.5】从n双互相不同的鞋中取出r只(r≤n),要求其中没有任何两只是成对的,共有多少种不同的取法?

这实际上是一种二次分配问题.即将r个相同的球放入n个不同的盒子,第i个盒子最多放ti个球,而该盒子又分为ni个相异的格子,每个格子最多只能放一个球,故还需要进行二次分配.如果第i个盒子中放进了ri个球,那么,对该盒子而言,二次分配时的方案数为.

例如,设甲、乙、丙3个班分别有30、28、22名学生,现把5本相同的书分给甲、乙、丙3个班,再发到个人手上,每人最多发一本.考虑将分给某班的某本书发给该班的同学A与将其发给同学B被认为是不同的分法,而且甲、乙两班最少1本,甲班最多5本,乙班最多6本,丙班最少2本,最多9本,问共有多少种不同的分配方案.

【例2.1.6】甲、乙、丙3人把n(n≥3)本相同的书搬到办公室,要求甲和乙搬的本数一样多,问共有多少种分配的方法.

解本问题即组合问题:从集合S={∞·e1,∞·e2,∞·e3}中可重复地选取n个元素,但要求e1与e2的个数一样多,求不同的选取方案数.

设想当n=1时,其分法只有1种,即甲和乙都分0本,丙分1本.当n=2时,其分法有2种:甲和乙都分0本(丙分2本)或甲和乙都分1本(丙分0本).当n=3时,也是2种分法.

当n=4或5时,分法为3种:即甲和乙都分0本、1本或2本

一般情形,甲分k本,乙也必须分k本,丙就只能分n-2k本.考虑将分配过程分为3步实现.第一步先选出2k本书,第二步将选出的书分给甲、乙各一半,第三步将剩下的书全分给丙.由于第二步属于二次分配,且只有一种分法,故可以将甲和乙视为一人,从而把问题转换为:将n本相同的书分给两个人,其中一人分得偶数本,求分配方法数.显然,本问题的母函数为

【例2.1.7】证明组合等式

证本例是母函数的另一种应用.意图说明普母函数除了能用于解决组合的求值问题之外,还能用来证明很多组合等式.

(3)因为

2.2母函数的性质

由于母函数与它的生成数列之间是一一对应的,因此,若两个母函数之间存在某种关系,则对应的生成数列之间也必然存在相应的关系.反之亦然.利用这类对应关系,常常能帮助我们构造出某些指定数列的母函数的有限封闭形式.特别地,还能得到一些求和的新方法.设数列{ak}、{bk}、{ck}的母函数分别为A(x)、B(x)、C(x),且都可逐项微分和积分

2.3指数型母函数

但是,注意到n集的r无重排列数和r无重组合数之间有如下关系:

从而有

定义2.3.1对于数列{ak}={a0,a1,a2,…},把形式幂级数

称为数列{ak}的指数型母函数,简称为指母函数,而数列{ak}则称为指母函数Ge(x)的生成序列.

说明

(1)ak的非零值可以为有限个或无限个.

(2)数列{ak}与母函数一一对应,即给定数列便得知它的指母函数;反之,求得指母函数则数列也随之而定.

(3)这里将指母函数只看做一个形式函数,目的是利用其有关运算性质完成计数问题,故不考虑“收敛问题”,即始终认为它是收敛的,而且是可“逐项微分”和“逐项积分”的.

(4)相应于同一数列{ak},一般G(x)≠Ge(x).

定理2.3.1设重集S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,则S的r可重排列的指母函数为

其中,r可重排列数为xr/r!之系数ar,r=0,1,2,…,n.

【例2.3.1】盒中有3个红球,2个黄球,3个蓝球,从中取4个球,排成一列,问共有多少种不同排列方案.

所以,从中取4个球的排列方案有70种.

类似于组合问题,令

即对全部排列方案进行分类枚举.可以看出,取1个球的3种排列方案为红、黄、蓝各分别取1个.取2个球的9种排列方案为:红红、黄黄、蓝蓝、红黄、黄红、红蓝、蓝红、黄蓝、蓝黄.其它情形依此类推.

这里需要说明的是:

(1)在例2.1.3中,利用普母函数可以将组合的每一种情况都枚举出来,但是对排列问题,指母函数却做不到,只能对排列进行分类枚举.正如例2.3.1这样,项ryb的系数6说明红、蓝、黄球各取一个时,有6种排列方案,但每一种方案具体是什么,则无法表示出来了.

推论1若S={e1,e2,…,en},则r无重排列的指母函数为

推论2若S={∞·e1,∞·e2,…,∞·en},则r无限可重排列的指母函数为

排列数为nr

推论3

S={n1·e1,n2·e2,…,nm·em},元素ei至少取ki个(ki≥0),则有

推论4S={n1·e1,n2·e2,…,nm·em

},令r=n,即得全排列数

【例2.3.2】五个数字1,1,2,2,3能组成多少个四位数?

由a4=30知能组成30个四位数.同时还知道能组成3个一位数,8个两位数,18个三位数等.

【例2.3.3】求1,3,5,7,9五个数字组成的n位数的个数(每个数字可重复出现),要求其中3,7出现的次数为偶数,1,5,9出现的次数不加限制.

【例2.3.4】把上例的条件改为要求1、3、7出现的次数一样多,5和9出现的次数不加限制.求这样的n位数的个数.

解设满足条件的数有bn个,与例2.1.6的分配问题类似,即将n个不同的球放入标号为1、3、5、7、9的5个盒子,其中盒子1、3、7中的球一样多.考虑把此3个盒子视为一个大盒子,大盒子中分为3个小盒子.问题即转化为将n个不同的球放入A、B、C这3个不同的盒子,其中盒子A里球的个数应为3k(k≥0),且A中的球第二次被分到3个不同的小盒子中,每个盒子恰好放入k个球,有种分法.所以,本问题的指母函数为

【例2.3.5】在例2.1.5中,若把所取出的r只鞋再排成一列,问共有多少种结果.

解此问题即是从集合S={e11,e12,e21,e22,…,en1,en2}的n类共2n个元素中不重复地取出r个元素排成一列,且同一类元素ei1,ei2不能同时出现(1≤i≤n).因此,其r个元素无重排列的指母函数应为

即不同的排列共有

从分配角度看问题,就是将r个不同的球放入n个不同的盒子,每个盒子最多放一个球,而且每个盒子中有两个相异的格子,故还需要进行二次分配.如果某个盒子中放进一个球,那么,二次分配时有两种可选的方案.

2.4正整数的分拆

定义2.4.1将一个正整数n分解成k个正整数之和称该分解是n的一个k分拆,并称ni

为分量.

此外,按照对诸ni

是否要考虑顺序,将分拆分为两类.例如5的两个4分拆:

若考虑ni

间的顺序,这两个分拆被认为是不同的,这样的分拆称为有序分拆.否则,不考虑顺序,这时可把右端按大小重新排列且看作是同一分拆,称为无序分拆.

2.4.1有序分拆

求n的k有序分拆的个数,相当于求一次不定方程(2.4.1)全体正整数解的组数,可对每个分量ni加以条件限制,例如1≤ni≤ri(i=1,2,…,k),于是可得如下结果.

定理2.4.1对于n的k有序分拆

其k有序分拆数数列{qk(n)}的母函数是

推论若对n的k有序分拆的各分量ni

没有限制,则其k有序分拆数数列{qk(n)}的母函数是且qk(n)=C(n-1,k-1).

2.4.2无序分拆

由前面的定义可以看出,在n的分拆中,如果不考虑各分量的顺序,为讨论方便起见,可把分拆后的各项数值从大到小加以排列,即有

满足以上条件的每一组正整数解(n1,n2,…,nk)就代表了一个n的k无序分拆,简称分拆,其分拆数记作pk(n),n1称为最大分项.

把n分拆为最大分项等于k,其分拆数相当于求不定方程

的整数解的组数.即整数n由1,2,…,k允许重复且k至少出现一次的所有(由条件式(2.4.4)限制的)组合数,其母函数为

其中展开式中xn

的系数即为n的最大分项等于k的分拆个数.

若最大分项小于或等于k,其分拆数相当于解不定方程

其分拆数列的母函数为

其中展开式中xn

的系数即为n的最大分项不超过k的分拆个数.

2.4.3弗雷斯(Ferrers)图

一个从上而下的k层格子,设mi为第i层的格子数,当mi≥mi+1(i=1,2,…,n-1),即上层的格子数不少于下层的格子数时,称之为Ferrers图.如图2.4.1所示.图2.4.1共轭Ferrers图

Ferrers图具有以下性质:

(1)每一层至少有一个格子;

(2)Ferrers图与式(2.4.3)说明的无序分拆是一一对应的,其中的对应关系是:第1层的格子数对应分项n1,第2层的格子数对应分项n2,……,依此类推.图2.4.1(a)就代表20的一种分拆,即20=7+5+5+2+1.

(3)将图形“转置”,即把行与列对调所得的图仍然是Ferrers图,称为原Ferrers图的共轭图(图2.4.1中的(b)是(a)的共轭图),或者说这两个图是一对共轭的Ferrers图.若某个Ferrers图与其共轭图形状相同,则称其是自共轭的.

定理2.4.2

(1)n的所有k分拆的个数等于把n分拆成最大分项等于k的所有分拆数;

(2)把n分拆成最多不超过k个数之和的分拆数等于把n分拆成最大分项不超过k的所有分拆数.

推论正整数n分拆成互不相同的若干个奇数的和的分拆数,等于有n个格子的自共轭的Ferrers图的个数.

证设

构造一Ferrers图,其第一行、第一列都是n1+1个格子,对应于2n1+1,第二行、第二列都是n2+1个格子,对应于2n2+1,依此类推.由此所得的Ferrers图是自共轭的.反过来也一样.例如

对应的Ferrers图如图2.4.2所示.图2.4.2n分拆为不同的奇数及其对应的自共轭的Ferrers图

2.4.4分拆数的估计

对于n的k无序分拆,当k任意时(k=1,2,…,n),n的所有分拆的个数称作n的分拆数,记作p(n),即

定理2.4.3正整数n的全部分拆总数数列{p(n)}的母函数是

当n较大时,计算p(n)是非常困难的,例如

下面给出p(n)的渐进公式和估值不等式.

定理2.4.4关于p(n)的计算,有

其中[x]表示将x四舍五入取整.

定理2.4.5设函数Q(n,m)表示正整数n的最大分项n1≤m的所有分拆数,则有

定理2.4.5实质上是函数Q(n,m)的递归定义,其原因如下:

(1)显然有Q(1,n)=Q(m,1)=1;

(2)因为最大分量n1实际上不能大于n,故m>n时,Q(n,m)=Q(n,n);

(3)由于在n的所有分拆中,其1分拆只有一个,即n=n1,而其它的分拆都是n1≤n-1;

(4)因为对于正整数n,最大分项为m的分拆数由以下两部分组成:一个是以m作为第一分项,其余分项之和等于n-m,且最大分项n2不超过m的分拆数Q(n-m,m);另一个是最大分项n1≤m-1的分拆数Q(n,m-1).

2.4.5应用

【例2.4.1】设有1克、2克、3克、4克的砝码各一枚,若要求各砝码只能放在天平的一边.问能称出哪几种重量?有哪几种可能方案?

解这是典型的正整数分拆问题.比如说可以称6克重的物品,使用的砝码可以是1克、2克、3克的三个砝码放在一起,也可以是2克和4克的两个砝码放在一起来称.即当最大分项不超过4时,6的无序不重复分拆只有两种

首先,将整数n分拆为最大分项不超