每日算法 — 使用java实现母函数：组合计数与递推关系的幂级数求解

算法概述

母函数（Generating Function，又称生成函数）是组合数学中极为强大的工具。它将一个序列编码为一个形式幂级数，使得复杂的组合计数问题转化为多项式运算问题。普通母函数将序列{aₙ}映射为幂级数A(x)=Σaₙxⁿ，通过对幂级数的代数操作即可求解原序列的通项或特定项。

核心原理

普通母函数的定义：对于序列{a₀, a₁, a₂, …}，其普通母函数为

A(x) = a₀ + a₁x + a₂x² + a₃x³ + …

关键性质：

1. 加法：两个序列对应项相加，母函数也相加
2. 乘法（卷积）：两个母函数相乘，结果中xⁿ的系数等于原序列的卷积
3. 求导：母函数求导后，xⁿ的系数乘以(n+1)
4. 特殊序列：
5. 全1序列 → 1/(1-x)
6. 自然数序列 → x/(1-x)²
7. 二项式系数 → (1+x)ⁿ

经典问题：整数拆分

给定整数n，求将n拆分为正整数之和的方案数（不考虑顺序）。母函数解法将每个正整数k视为可选0次、1次、2次…，对应因子(1+xᵏ+x²ᵏ+…)=1/(1-xᵏ)，总母函数为∏(1/(1-xᵏ))。

Java完整实现

import java.math.BigInteger;
import java.util.Arrays;

/**
 * 母函数（生成函数）组合计数实现
 * 应用场景：整数拆分、组合方案计数、递推关系求解
 */
public class GeneratingFunction {

    /**
     * 整数拆分：求将n拆分为正整数之和的方案数
     * 使用母函数：G(x) = ∏(1/(1-x^k)) for k=1,2,3,...
     * 实际计算时展开为多项式乘法
     * @param n 待拆分的整数
     * @return 拆分方案数
     */
    public static BigInteger partitionCount(int n) {
        // dp[i] 表示拆分为i的方案数，即母函数中x^i的系数
        BigInteger[] dp = new BigInteger[n + 1];
        Arrays.fill(dp, BigInteger.ZERO);
        dp[0] = BigInteger.ONE; // 拆分为0的方案数为1

        // 依次考虑每个正整数k作为拆分的组成部分
        // 对应母函数因子 (1 + x^k + x^(2k) + x^(3k) + ...)
        for (int k = 1; k <= n; k++) {
            for (int j = k; j <= n; j++) {
                dp[j] = dp[j].add(dp[j - k]);
            }
        }

        return dp[n];
    }

    /**
     * 有限物品组合问题：给定若干种物品，每种物品有数量限制，求凑成金额n的方案数
     * @param items 每种物品的面值
     * @param limits 每种物品的数量限制（-1表示无限）
     * @param target 目标金额
     * @return 方案数
     */
    public static long combinationCount(int[] items, int[] limits, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;

        for (int i = 0; i < items.length; i++) {
            int value = items[i];
            int limit = limits[i];

            // 逆序遍历避免重复计数
            for (int j = target; j >= 0; j--) {
                if (dp[j] > 0) {
                    // 枚举选取该物品的个数
                    int maxCount = (limit == -1) ? (target - j) / value : Math.min(limit, (target - j) / value);
                    for (int c = 1; c <= maxCount; c++) {
                        dp[j + c * value] += dp[j];
                    }
                }
            }
        }

        return dp[target];
    }

    /**
     * 母函数多项式乘法：计算两个多项式的乘积
     * 结果中x^k的系数 = Σa[i]*b[k-i]
     * @param a 第一个多项式的系数数组
     * @param b 第二个多项式的系数数组
     * @return 乘积多项式的系数数组
     */
    public static long[] polynomialMultiply(long[] a, long[] b) {
        int n = a.length, m = b.length;
        long[] result = new long[n + m - 1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i + j] += a[i] * b[j];
            }
        }

        return result;
    }

    /**
     * 使用母函数求解斐波那契数列通项
     * F(x) = x / (1 - x - x^2)，通过多项式展开获取系数
     * @param n 求第n项（从0开始）
     * @return 斐波那契数列第n项
     */
    public static long fibonacciByGF(int n) {
        if (n <= 1) return n;

        // 模拟 1/(1-x-x^2) 的展开，即递推关系
        long[] coeff = new long[n + 1];
        coeff[0] = 1;
        // 1/(1-x-x^2) = ΣF[n+1]*x^n
        // 使用递推：a[n] = a[n-1] + a[n-2] for n>=2, a[0]=1, a[1]=1
        if (n >= 1) coeff[1] = 1;
        for (int i = 2; i <= n; i++) {
            coeff[i] = coeff[i - 1] + coeff[i - 2];
        }

        return coeff[n - 1]; // F[n] = coeff[n-1]
    }

    /**
     * 骰子问题：投掷n个骰子，求点数之和为s的方案数
     * 母函数：(x + x^2 + ... + x^6)^n
     * @param n 骰子个数
     * @param s 目标和
     * @return 方案数
     */
    public static long diceSumWays(int n, int s) {
        // 单个骰子的母函数：x + x^2 + x^3 + x^4 + x^5 + x^6
        long[] single = {0, 1, 1, 1, 1, 1, 1};
        long[] result = {1}; // 初始为1（0个骰子的母函数）

        for (int i = 0; i < n; i++) {
            result = polynomialMultiply(result, single);
        }

        return (s < result.length) ? result[s] : 0;
    }

    public static void main(String[] args) {
        // 测试整数拆分
        for (int n = 1; n <= 10; n++) {
            System.out.println("p(" + n + ") = " + partitionCount(n));
        }

        // 测试组合计数：用1元、2元、5元凑成10元，数量不限
        int[] items = {1, 2, 5};
        int[] limits = {-1, -1, -1};
        System.out.println("\n凑成10元的方案数: " + combinationCount(items, limits, 10));

        // 测试骰子问题：2个骰子点数和为7
        System.out.println("\n2个骰子点数和为7的方案数: " + diceSumWays(2, 7));

        // 测试斐波那契母函数
        System.out.println("\n斐波那契数列前10项:");
        for (int i = 0; i < 10; i++) {
            System.out.print(fibonacciByGF(i) + " ");
        }
    }
}

复杂度分析

应用场景

• 组合计数：选举问题、分配问题、路径计数
• 概率生成函数：随机变量的期望和方差计算
• 递推关系求解：将线性递推转化为有理函数展开
• 编码理论：校验多项式与生成多项式设计

母函数将离散组合问题提升到连续代数框架，是算法竞赛和理论计算机科学中不可或缺的思维工具。