1、 母函数有着广泛的应用，它不仅可以用来处理排列组合的计数问题、整数分拆问题，而且还可以用来证明(或推导)各种有用的组合恒等式。4.34.3母函数在排列、组合中的应用母函数在排列、组合中的应用 从这节开始我们分别讨论母函数在某些问题中的应用。特别是在第五章讨论的递归关系中有特别是在第五章讨论的递归关系中有着重要的应用。着重要的应用。同样，从这三个不同的物体中选取两个有三种方法，或者选取a和b，或者选取b和c，或者选取c和a。首先首先，我们考虑下列事实。令a,b,c表示三个不同的物体。显然有三种方法从这三个不同的物体中选取一个，或者选a，或者选b，或者选c我们把这些可能的选取象征性地记为 a+b+
2、c我们把这些可能选取也象征性地记为 ab+bc+ca 而从这三个不同的物体中选取三个只有一种方法，把这种可能的选取象征性地记为 abcabc 考虑多项式 (1+ax)(1+bx)(1+cx)(1+ax)(1+bx)(1+cx)=1+(a+b+c)x =1+(a+b+c)x1 1+(ab+bc+ca)x+(ab+bc+ca)x2 2+(abc)x+(abc)x3 3 从这个多项式可以看出，以上所有的可能选取方法都作为x的幂的系数被表示出来了。下面，利用乘法规则和加法规则对上面的多项式予以解释。特别是，xi的系数就是从三个不同的物体中选取i个物体的方法的表示。这并不是偶然的巧合。对物体a,因子(1
3、+ax)象征性地表示有两种选取方法:不选取 a，或选取 a。对于(1+bx),(1+cx)可作类似的解释。这样，(1+ax)(1+bx)(1+cx)就表明：对三个不同的物体a,b,c，其选择方法是，不选取a或选取a；不选取b或选取b；不选取c或选取c。其中x仅是一个形式变量。x0 的系数表明不选取 a,x1 的系数表明a被选取。于是这三个因子的乘积中x的幂指数就表示被选取的物体的个数，而对应的系数系数则表明了所有可能的选取方法。因此，由普通母函数的定义知，三个因子 的乘积(1+ax)(1+bx)(1+cx)就是选取物体a，b，c的所有不同方法的普通母函数。如果由于某种实际的需要，我们只对可能的
4、选取方法的个数感兴趣，而不是对不同的选取方法感兴趣，则可令a=b=c=1。于是有于是有(1+x)(1+x)(1+x)=(1+x)3=1+3x+3x2+x3该多项式表明该多项式表明 只有一种方法 从三个物体中一个也不选取，有三种方法 从这三个物体中选取一个，有三种方法 从这三个物体中选取两个。有一种方法 这三个物体中选取三个。一般说来，考虑多项式 103 313 323 133rnrnxrnxxxx 0)1()1()1)(1(对于这个多项式可作上面n=3时的同样的解释。也就是说，从n个不同的物体中选其r个物体，其方法数为(1+x)n的幂级数展开式中xr的系数 。rn 以上讨论的是从n个不同物体中
5、选取r个物体(每个物体至多选取一次)的简单情形。当当从n个不同的物体中，允许重复选取r个物体时，上面的情况就可作如下的上面的情况就可作如下的推广。推广。那么那么，类似地，我们可以用因子(1+x+x2)象征性地表示某一物体可以不选，或者选一次，或者选两次。也就是说某一物体至多选两次。同样，用因子(1+x+x2+x3+)象征性地表示某一物体可以不选，或者选一次，或者选两次，或者选三次，。那么那么，(1+x+x2+x3+)n的幂级数展开式中，xr的系数ar就表示从n个不同的物体中允许重复地选取r个物体的方式数。由于因子(1+x)象征性地表示某一物体可以不选，或者只选一次。下面，我们举例加以说明。下面
6、，我们举例加以说明。rrnrnF1),(例例1 1 证明从n个不同的物体中允许重复地选取r个物体的方式数为 这个问题可以等价地叙述为：证明重集B=b1,b2,bn的r-组合数为 。这就是定理1.6已经证明过的结论。rrn1 下面用母函数法证明：设ar表示从n个不同物体中允许重复选取r个物体的方式数，由上面的分析可知，序列(a(a0 0,a,a1 1,a,ar r,)的普通母函数为nnxxxxf 11)1()(2rrrrrrxrrnxrrnnnxrrnnn 0001!)1()1()(!)1()1(rrnrnFar1),(例例2 2 证明从n个不同的物体中允许重复地选取r个物体，但每个物体至少出现
7、一次的方式数为 11nr证明证明：设ar表示从n个不同物体中允许重复地选取r个物体，但每个物体至少出现一次的方式数，则序列(a(a0 0,a,a1 1,a,ar r,)的普通母函数为nnnrxxxxxxxf)1()()(22 )0(1111111110000 knnkxnrxnrxnrrxrrnxrrnxxxrrrnrrrnrrrrnnn时，时，注意，当注意，当 11nrar故有故有 解解：设a2r为所求的方式数，由于每个物体出现偶数次。故可用因子(1+x2+x4+)表示某一物体可以不选，或选取两次，或选取4次，。例例3 3 求从n个不同的物体中允许重复地选取2r个物体，但每个物体出现偶数次的
8、方式数。因此序列(a(a0 0,a,a1 1,a,ar r,)的普通母函数为nnxxxxf 24211)1()(02264211322111rrrxrrnxrrnxnxnxn rrnar12故有故有例例4 4 在一个书架上共有16本书，其中4本是高等数学，3本是普通物理，4本是数据结构，5本是离散数学。求从中选取r本书的方式数，其中r=12。解解：这个问题实际上是求重集 B=4M,3P,4S,5D的r-组合数也是3.2节中例1的问题。设ar是选取r本书的方式数。由于高等数学最多只能选4本，普通物理最多只能选3本，数据结构最多只能选4本，离散数学最多只能选5本。故序列故序列(a(a0 0,a,a
9、1 1,a,ar r,)的普通母函数为的普通母函数为)1)(1)(1()(43232432xxxxxxxxxxxxf )1(5432xxxxx 98765432768076655034201041xxxxxxxxx161413121110420345065xxxxxx 这个答案与3.2节中例1用容斥原理所求的结果是一致的。取f(x)展开式中xr的系数即为所求的方式数。当r=12,x12的系数为34，即 a12=34解解：这个问题实际上是求重集 B=2nA,2nB,2nC的3n组合数。设ar为所求的方式数，则序列(a(a0 0,a,a1 1,a,ar r,)的普通母函数为 例5 现有2n个A，2
10、n个B和2n个C，求从它们之中选出3n个字母的不同的方式数31232211)1()(xxxxxxfnn 0312)(!)2()4)(3(1)1(kknxkkx 0362412!)2(431)331(kknnnxkkxxxkknnnxkxxx 036241222)331(213223nn 2132233nnan在上式中x3n的系数为故当r=3n时有rnrnxrnx 0)1(nrrrnrnrxrnpxrnx00!),()1(以上，我们讨论了普通母函数在组合计数问题中的应用。下面说明指数母函数在排列计数问题中的一些应用。我们已知道是从n个不同的物体中选取r个物体的组合数ar所成的序列的普通母函数。利
11、用式(1.7)将上式变形有而(1+x)=(1+x1/1!)象征性地表示某一物体在 排列中可以不选取，或者选取一次。由此我们得到启发，某一物体在排列中可以不取，或取一次，或取两次，或取r次可用如下形式表示：!212rxxxr 这表明从n个不同的物体中选取r个物体的排列数恰好是xr/r!的系数。特别是特别是，如果某物体的重复次数是时，则上式的形式变为 !212rxxxr!5!4!3!25432xxxx 同样地，如果某一物体在排列中至少取两次，至多取五次，则可用下面的形式表示 证明证明：这个问题实质上是证明重集B=b1,b2,bn的r排列数为nr。这就是1.2节定理1.3已经证明过的结论。这里用母函
12、数的方法证明。下面，我们举例说明。例例6 6 证明从n个不同的物体中允许重复地选取r个物体的排列数为nr 设ar为所求的排列数，由上面的分析知，序列(a(a0 0,a,a1 1,a,ar r,)的指数母函数为nrerxxxxf)!21()(2 !)(0rxneerrrnxnx rrna 故有故有 解解：这个问题等价于求重集B=1,1,3,3,5 5，7 7，9)9)的r排列数。其中要求7，9出现偶数次。例例7 7 求1，3，5，7，9五个数字组成r位数的个数。其中要求7，9出现的次数为偶数。其余数字的出现不加限制。32242)!21()!4!21()(xxxxxfe !3!21!)1(!3!2
13、13232nxxxxenxxxxenxnnx而而故故 !4!21242xxeexx设所求的r-排列数为ar，则序列(a0,a1,ar,)的指数母函数为 32)(2)(xxxeeeexf !)1325(41!32!541)2(41000035rxrxxrxreeerrrrrrrrrrrrxxx)1325(41 rrra故故 所以有所以有 例例8 8 用红、白和绿三种颜色给1n棋盘中的正方形着色，要求偶数个正方形着红色，而着白色和绿色的正方形个数不加限制，求不同的着色方式数。解解：若用R，B B和V分别表示红红、白白和绿绿三种颜色，则该问题实际上是求重集B=R R,B,B,V V的n排列。其中要求
14、R出现偶数次。设an为所求的方式数。定义a0=1，于是序列(a a0 0,a,a1 1,a,an n,)的指数母函数为2242)!21)(!4!21()(xxxxxfe!)13(21!321)(21)(2100032nxnxnxeeeeennnnnnnnxxxxx )13(21 nna故有故有 解解：这是第三章容斥原理的习题8。这里用母函数法来求解。这个问题实际上是求重集B=1,2,3，5，6，7，8，9 的n排列个数，其中要求数字3，8，9至少出现一次，而其他的数字则不加限制。例例9 9 在所有的n位数中，包含数字3，8，9，但不包含数字0，4的数有多少?设符合题意的数有an个，则序列(a0
15、,a1,an,)的指数母函数为 5232)!21()!2()(xxxxxfe!)563738(33)()1(0567853nxeeeeeennnnnnxxxxxx 故有故有 这个结果与用容斥原理所得的结果是一致的。nnnnna563738 解解：设ar为所求的符合题意的个数。由于1出现次数与2出现的次数的和为偶数，这有两种情况：(1)1出现的次数与2出现的次数都为偶数。(2)1出现的次数与2出现的次数都为奇数。例例1010 求1，2，3，4，5五个数字组成的r位数的个数，其中要求1出现的次数与2出现的次数的和必须是偶数。故由加法规则知，序列(a0,a1,，ar)的指数母函数为 32242)!21()!4!21()(xxxxxfe32253)!21()!5!3(xxxxxxxxxxxeeeeee323222!)15(210nxnnn )15(21nna故有故有
