【概述】

母函数是求解组合数学中计数问题的重要方法，效率高，编程规范，容易实现。

对于序列 ，定义  为序列  的母函数。

例如： 就是  的母函数

也就是说，我们可以利用  来讨论序列 的性质，还可以引入适当的函数，将问题简化，把复杂的问题变成形式上的初等代数运算。

【普通型母函数】

1.杨辉三角与母函数

杨辉三角中第 n 行的数字就是  的展开式从低项到高项的各项系数。

而 

                    

所以，有如下形式的杨辉三角：

将 (1+x) 与选择物品联系起来，在构造和分析一个母函数时，1 一般看成 ，用于表示没有选取一个物品， 可以看成选择了一个物品。因此  可以对应于从 n 件物品中选取了若干件物品的情况。

在一个具体的物品选择中，如果没有选择第 i 件物品，则相当于从第 i 个括号中选取了  ，如果选择了第 i 件物品，这相当于从第 i 个括号中选择了 ，这样，在  的展开式中， 前面的系数就是从 n 件物品选取了 i 件物品的所有组合情况的总数，即 

2.普通母函数

1）母函数

给定数列 ，构造一个函数 ，称 F(x) 为数列  的母函数，其中，序列  只作为标志用，称为标志函数。

2）母函数的一般形式

标志函数最重要的形式是 ，这种情况下的母函数一般形式为：

3）母函数定理

设从 n 元集合  中取 k 个元素的组合是 ，若限定元素  出现次数的集合为 ，则该组合数序列的母函数为：

4）常见母函数

5）例题

有重量为 1，3，5 的砝码各两个，求：

① 可以称出多少种质量不同的物品？

② 若要称出重量为 7 的物品，所用砝码有多少种本质不同的情况？

分析：

根据母函数定理，构造母函数：

其中，第一个括号的 1 表示不用重量为 1 的砝码，x 表示用 1 个重量为 1 的砝码， 表示用 2 个重量为 1 的砝码，第 2、3 个括号中的含义类似。

将多项式展开后，得到诸如  之类的多项式，它表示用 2 个重量为 1 的砝码，0 个重量为 3 的砝码，1 个重量为 5 的砝码，可以称出一个重量为 7 个物品。

显然，将 G(x) 展开并合并同类项后，有多少个非 0 系数项就代表了可以称出多少种不同重量的物品，而相应的  前面的系数就表明了称出重量为 i 的物品可选砝码方案数。

故：

因此，问题 ① 的解为：19，问题 ② 的解为：2

【指数型母函数】

1.指数型母函数定理

从多重集合  中选取 k 个元素的排列中，若限定元素  出现的次数集合为 ，则该组合数序列的母函数为：

2.标志函数

普通型母函数的标志函数为：

指数型母函数的标志函数为：

3.物理意义

指数型母函数的标志函数可以这样理解：对于  表示在一个方案中某个元素出现了 j 次，而在不同的位置中的 j 次出现是相同的，所以在排列计算总数时，只应算作一次，由排列组合的知识知道，最后的结果应该除以 

4.简化形式

指数型母函数在使用过程中，一般会用到高等数学中的  的泰勒展开式：

因此，指数型母函数可以简化为：

，其中，只有  是所需的结果。

5.例题

设有六位数字，其中三个数字1，两个数字6，一个数字8，求能组成多少个四位数？

分析：

这个题实际上是求  中取四个多重集排列数问题，其指数型母函数为：

           

因此，可以取38个四位数