1、ACM程序设计第十二讲 -组合数学湖南工学院 张新玉主要内容 1 母函数及其 应 用 2 群的概念 3 polya定理 * 3研究以下 多项式乘法 ：可以看出：x2项的系数 a1a2+a1a3+.+an-1an中所有的项包括 n个元素a1， a2， an中取两个组合的全体；同理： x3项系数包含了从 n个元素 a1， a2， an中取 3个元素组合的全体；以此类推。 (13 1)* 4若令 a1=a2= =an=1， 在（ 8-1）式中a1a2+a1a3+.+an-1an项系数中每一个组合有1个贡献，其他各项以此类推。故有：（ 13 2）特例：* 5母函数定义： 对于序列 a0， a1， a2
2、， 构造一函数： n 称函数 G(x)是序列 a0， a1， a2， 的母函数* 6For example:(1+x)n是序列C(n,0),C(n,1),.,C(n,n)的母函数。 如若已知序列 a0， a1， a2， 则对应的母函数 G(x)便可根据定义给出。反之，如若已经求得序列的母函数 G(x)， 则该序列也随之确定。 序列 a0， a1， a2， 可记为 an 。 * 7实 例 分 析* 8例 1：若有 1克、 2克、 3克、 4克的砝码各一 枚，能称出哪几种重量？各有几种可能方案？ 如何解决这个问题呢？考虑构造母函数。如果用 x的指数表示称出的重量，则：1个 1克的砝码可以用函数 1
3、+x表示，1个 2克的砝码可以用函数 1+x2表示，1个 3克的砝码可以用函数 1+x3表示，1个 4克的砝码可以用函数 1+x4表示，* 9几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 从上面的函数知道： 可称出从 1克到 10克，系数便是方案数。例如右端有 2x5 项，即称出 5克的方案有 2：5=3+2=4+1；同样， 6=1+2+3=4+2； 10=1+2+3+4。故称出 6克的方案有 2，称出 10克的方案有 1 * 10例 2： 求用 1分、 2分、 3分的邮票贴出不同数值的方案数 因邮票允许重复，故母函数为：n 以展开后的 x4为例，其系数为 4，即 4拆分成 1、 2、 3之和的拆分数为 4；n 即 ： 4=1+1+1+1=1+1+2=1+3=2+2
