母函数解题法：砝码组合与邮票计数

母函数模板是一种在数学和计算机科学中广泛应用的工具，特别是用于解决组合问题和计数问题。它通过将问题转化为幂级数的形式，将加法法则与幂的乘法对应起来，提供了一种直观且高效的解题方法。以下内容主要围绕两种具体问题来阐述母函数的应用。 首先，我们来看一个关于砝码的问题。题目给出1克、2克、3克和4克的砝码各一枚，要求找出所有可能的称重组合。我们用母函数1+1*x^1, 1+1*x^2, 1+1*x^3, 和1+1*x^4分别表示每个砝码的使用情况。其中，1*x^n代表使用n克的砝码。例如，1+x^2表示可以不使用2克砝码（x^0）或使用2克砝码（x^2）。将这些函数相乘，得到(1+x)(1+x^2)(1+x^3)(1+x^4)，其展开后可以看到从1克到10克的所有可能称重以及对应的方案数。 对于每一种权重，系数即表示相应方案的数量。例如，x^5的系数2表示5克的组合有两种：3克和2克，或者4克和1克。这种母函数的方法简洁明了地展示了称重的多样性。 第二种情况涉及用1分、2分、3分的邮票贴出不同数值的方案数。与第一个问题相比，这里的区别在于邮票的面额不是有限的，而是可以无限增加。通过同样的母函数方法，我们可以计算不同面额邮票组合的方案数。以x^4为例，其系数为4，意味着可以表示4分邮票的不同组合方式，如1+1+1+1（四个1分），1+1+2（一个1分和两个2分），1+3（一个1分和三个3分），或者2+2（两个2分）。这里引入了两个概念，“整数拆分”指的是将一个整数分解成多个非负整数之和，“拆分数”则是指这个分解的组合数量。 总结来说，母函数模板提供了一种通用的策略来解决涉及组合和计数的问题，它通过将问题映射到幂级数的形式，巧妙地利用数学工具来计算可能的解决方案。无论是有限的砝码组合还是无限的邮票面额，母函数都能帮助我们系统地理解和解决这些问题。