用母函数求解排列问题

［摘 要］ 母函数是组合数学中的一个重要概念，用母函数来处理中学数学中的一些排列问题，其可操作性强，学生容易理解. 文章先介绍指数型母函数的相关内容和定理，然后结合实例给出其应用.

［关键词］ 排列问题；母函数；指数型母函数；理解；应用

计数问题在日常生活、生产中普遍存在. 计数问题属于组合问题，而组合中有一个重要概念——母函数（也叫发生函数、生成函数）［1］. 指数型母函数（简称指母函数）正是将复杂的计数问题简单化的一个工具，利用指母函数可以轻松求解排列问题.

预备知识

定义1 设a，a，…，a，…是一个给定的数列，我们称形式幂级数

f（x）=xn=a+ax+x2+x3+…+xn+…①

为这个数列的指数型母函数，简称指母函数［2］.

例如，数列1，1，1，…，1，…的指母函数是f（x）=xn=1+x++…++…. 这个指母函数非常重要，我们专门用f（x）=ex来记它，即f（x）=ex=1+x++…++….

规定：在进行这些运算时，把形式幂级数看成幂级数，然后按照幂级数的运算法则去运算.

定义2 设f（x）=xn和g（x）=xn是两个形式幂级数，则

f（x）±g（x）=xn，f（x）·g（x）=xn（其中c=Cakbn-k）.

定理1 ex·ey=ex+y.

在定理1中，取y=x，则（ex）2=e2x，即

=xn.

推论1 （ex）m=emx，即

=xn.

在定理1中，取y=-x，则ex·e-x=1，即=e-x. 由ex=1+DaiWAzYeH5rdxl986iFvKQ==x++…++…，e-x=1-x+-…+（-1）n+…，得到：

推论2 ex+e-x=2

1+++…++…

，ex-e-x=2

x+++…++…

.

注：对于指数幂ax（a>0，且a≠1），显然ax·ay=ax+y. 从定理1可以看出，ex·ey=ex+y具有指数幂的运算性质. 这就是称式①为指母函数的原因.

用指母函数求解排列问题

排列问题，困难在于对问题背景的理解，这是一个数学化过程，需要通过不同情境加强训练、加深理解.我们先来看看下列三类排列问题.

问题1 （不许重复的排列）从n个不同的物体中，任意取出r个作排列，不许重复，问有多少种不同的排法？

问题2 （允许无限重复的排列）从n个不同的物体中，任意取出r个作排列，允许重复，问有多少种不同的排法？

问题3 （允许有限重复的排列）设n个物体中，有n个物体A，n个物体A，…，n个物体A，n+n+…+n=n，现从中任取r个作排列，问有多少种不同的排法？［3］

分析 问题1的解答很简单，不同的排列的总数为A=n（n-1）…（n-r+1）. 特别地，当r=n时，不同的排列的总数为A=n（n-1）…3×2×1=n！. 这在中学课本上已经很熟悉了.

问题2的解答也不困难.因为允许重复，所以每个排列的r个位置上都有可能放n个不同物体中的任何一个，即每个位置都有n种可能，因此不同的排列的总数为nr［4］.

解答困难的是问题3，因为每个物体重复的次数是有限的，这给问题带来了复杂性.但如果考虑r=n的情形，问题还不算太难.

定理2 设n个物体中，有n个物体A，n个物体A，…，n个物体A，n+n+…+n=n，则这n个物体不同的排列的总数为.

证明 由于对每个排列来说，n个物体A，n个物体A，…，n个物体A都出现在排列中，因此n个物体排列的总数为n！，而在这n！个排列中有很多的排列是一样的，例如n个物体A任意交换位置，若其他物体不动，这样得到的排列全是一样的，这种相同的排列有n！个. 同理，对物体A，A，…，A，也会有同类情况. 去掉这些相同的排列后，真正不同的排列的总数为.

注：这是问题3中当r=n时的解答.最困难的是r<n的情形，这没有一般公式，而指母函数是解决这类问题的有力工具.

定理3 设n个物体中，有n个物体A，n个物体A，…，n个物体A，n+n+…+n=n，从这n个物体中任取r（r<n）个物体，不同的排列的总数记为a，则数列｛a｝的指母函数为f（x）=

1+x++…+

1+x++…+

…

1+x++…+

②.

证明 让第i个括号代表第i个物体A（i=1，2，…，k）.从第一个括号中取出项，解释为“取出3个物体A”；从第二个括号中取出项，解释为“取出4个物体A”；其余类似.

现在研究式②的展开式中的系数.

合并同类项前，式②的展开式中的是由各个括号中的项相乘而来的：··…·=，这里0≤m≤n，0≤m≤n，…，0≤m≤n，而且m+m+…+m=r. 故··…·=·. 由此可知，的系数是③，而且m+m+…+m=r.

根据定理2可知，式③恰好就是这r个物体不同的排列的总数：在这r个物体中有m个A，m个A，…，m个A，这说明乘积··…·就对应一种排列. 由于m（i=1，2，…，k）可以取遍0，1，2，…，n（i=1，2，…，k）中的所有整数，因此合并同类项后，的系数就表示从这n个物体中取出r个物体的不同的排列的总数.这就证明了式②就是数列｛a｝的指母函数.

在此我们可以把定理3推广到更一般的情形：

定理4 设A=｛a，a，…，a｝，M，M，…，M均为非负整数集的子集，从A中可重复地选取r个元素作排列. 如果a可重复选取的全部次数为M（k=1，2，…，n），记所有可能的排列数为er，则数列｛er｝（r≥0）的指母函数为f（x）=

…

. 将指母函数解析式展开，的系数就是所求的排列数e.

证明留给读者完成.

指母函数应用举例

题1 将8个不同的球分发给4个不同的班级，要求每个班至少分得一个球，问有多少种不同的分法？

解析 将8个不同的球排成一列，4个班依次编号为1，2，3，4.对于一个满足条件的分法，若把某个球分给编号为i的班，就在该球所排的位置上填上i，则得到｛1，2，3，4｝的一个“8可重”排列（即从集合｛1，2，3，4｝中可重复地选取8个元素作成排列）. 由于每个班至少分得一个球，所以每个数至少出现一次，即每个数出现的次数都属于集合｛1，2，3，…｝. 将n个不同的球分给4个不同的班且每个班至少分得一个球的分法数记为a，由定理4可知数列｛a｝（n≥1）的指母函数为f（x）=

x+++…

=（ex-1）4=e4x-4e3x+6e2x-4ex+1=xn-4xn+6xn-4xn+1=（4n-4×3n+6×2n-4）+1. 由此可得，的系数a=48-4×38+6×28-4=40824. 所以，共有40824种不同的分法.

题2 用数字1，2，3，4作六位数，每个数字在六位数中出现的次数不得大于2，问可作出多少个不同的六位数？

解析 这是排列问题，每个数字出现的次数都属于集合｛0，1，2｝. 设所求为N，由定理4可知，N是指母函数f（x）=

1+x+

的展开式中的系数，而

1+x+

=［x2+（2x+2）］4=［x8+4x6（2x+2）+6x4（2x+2）2+4x2（2x+2）3+（2x+2）4］，所以N=（4×2+6×22）=1440.

题3 把n（n≥1）个彼此不同的球放到4个不同的盒子A，A，A，A中，要求A有奇数个球，A有偶数个球，问不同的放球方法有多少种？

解析 设不同的放球方法有a种.因为要求A有奇数个球，A有偶数个球，A，A中球的个数没有限制，所以A盒子出现的球的个数属于集合｛1，3，5，…｝，A盒子出现的球的个数属于集合｛0，2，4，…｝，A，A盒子出现的球的个数都属于集合｛0，1，2，3，…｝.

由定理4可知，数列｛a｝的指母函数是f（x）=

x+++…

1+++…

1+x+++…

.

由推论1和推论2可得f（x）=··（ex）2=（e4x-1）=·=. 比较（n≥1）的系数，得a=4n-1.

结束语

母函数分为普通型母函数（简称普母函数）和指数型母函数（简称指母函数）.普母函数主要应用于求解组合问题，而指母函数则主要应用于求解排列问题.高中阶段的排列问题，有些是难以处理的，这时可借助指母函数来求解. 利用指母函数求解排列问题，学生容易理解，而且可操作性强，是处理排列问题的好方法.

参考文献：

［1］ 李鸿昌，徐章韬. 用母函数理解组合问题［J］. 数学通讯，2023（10）：59-61+66.

［2］ 曹汝成. 组合数学［M］. 广州：华南理工大学出版社，2000.

［3］ 刘会科. 母函数在组合计数中的应用［J］. 数理化解题研究，2016（13）：16-17.

［4］ 高仕学. 用母函数法统一解决三类排列与组合问题［J］. 课程教育研究，2017（07）：161.